Intereting Posts

condition for a cubic polynomial to have a real root
If $\int_{0}^{\infty} f(x) \, dx $ converges, will $\int_{0}^{\infty}e^{-sx} f(x) \, dx$ always converge uniformly on $[0, \infty)$?
Multiplicative group of integers modulo n definition issues
$\cos^n x-\sin^n x=1$
Evaluating a logarithmic integral in terms of trilogarithms
Does $\wp(A \cap B) = \wp(A) \cap \wp(B)$ hold? How to prove it?
Hypersurfaces meet everything of dimension at least 1 in projective space
How to prove that $\frac{r}{R}+1=\cos A+\cos B+\cos C$?
Mean Value property for harmonic functions on regions other than balls/spheres
Entire, $|f(z)|\le1+\sqrt{|z|}$ implies $f$ is constant
When the approximation $\pi\simeq 3.14$ is NOT sufficent
Do there exist an infinite number of 'rational' points in the equilateral triangle $ABC$?
A comparison between the fundamental groupoid and the fundamental group
Convergence of $\int f dP_n$ to $\int f dP$ for all Lipschitz functions $f$ implies uniform integrability
How far are the $p$-adic numbers from being algebraically closed?

How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $?

Please give me some ideas. Thank you.

- What is the millionth decimal digit of the $ 10^{10^{10^{10}}} $-th prime?
- Deciding if a number is a square in $\Bbb Z/n\Bbb Z$
- Find $N$ when $N(N - 101)$ is the square of a positive integer
- What is special about the numbers 9801, 998001, 99980001 ..?
- What is the smallest unknown natural number?
- Product of three consecutive positive integers is never a perfect power

- A multiplication algorithm found in a book by Paul Erdős: how does it work?
- Where does the constant increase by 2 of differences between integer square values come from?
- Expressing a Non Negative Integer as Sums of Two Squares
- Multiplication Table with a frame and picture of equal sum
- parametric solution for the sum of three square
- Proving for $n \ge 25$, $p_n > 3.75n$ where $p_n$ is the $n$th prime.
- Proving the equivalency of Principle of Mathematical Induction and Well Ordering Principle
- Confusion on the proof that there are “arbitrarily large gaps between successive primes”
- A 10-digit number whose $n$th digit gives the number of $(n-1)$s in it
- Prove that the number 14641 is the fourth power of an integer in any base greater than 6?

You use the extended Euclidean algorithm as so:

$$17 = 1 \cdot 13 + 4$$

$$13 = 3 \cdot 4 + 1$$

Therefore

$$1 = 13 – 3\cdot 4$$

$$1 = 13 – 3 \cdot (17 – 1\cdot 13)$$

$$1 = 4 \cdot 13 – 3 \cdot 17$$

$$4 \cdot 13 – 1 = 3\cdot 17$$

$$x = 4$$

@lab’s method is systematic and dependable, but for small prime moduli, I find trial and error to work very well. Think of multiples of $13$ till you get one that’s $1$ more than a multiple of $17$.

Another technique that I use especially when I’m doing extensive computations modulo a particular prime $p$ is to find (again by trial and error) a primitive element modulo $p$, that is a generator of the (cyclic) group of nonzero residues. As it happens, $3$ works for $p=17$, that is, the powers of $3$ exhaust all nonzero residues modulo $17$. Then you write down what the powers are in a list: $1$, $3$, $9$, $10$, $13$, $5$, $15$, $11$, $16=-1$, $-3$, etc., and you see that $3^4=13$ and $3^{-4}=3^{12}=4$, so that your desired answer is $4$. For a simple, single question like yours, this method is overkill, but it does come in handy for more extensive hand computations.

We can rewrite our congruence as $-4x\equiv 1\pmod{17}$, or equivalently $4x\equiv -1\pmod{17}$. But this can be rewritten as $4x\equiv 16\pmod{17}$, which has $x\equiv 4\pmod{17}$ as its only solution.

A system approach is to find integers $s$ and $t$ (via the Euclidean algorithm) such that $13s + 17t = 1$ (note that we can do this as $\gcd(13,17) = 1$). Then,

$$1 = 13s + 17t \equiv 13s \pmod{17}$$

so that $s = 13^{-1} \pmod{17}$.

$\rm mod\ 17\!:\,\ x\equiv \dfrac{1}{13}\,\equiv\,\dfrac{1}{-4}\,\equiv\,\dfrac{4}{-16}\,\equiv\,\dfrac{4}{1} $

**Remark** $\ $ We used Gauss’s algorithm for computing inverses $\rm\:mod\ p\:$ prime.

$$\frac{17}{13}=1+\frac4{13}=1+\frac1{\frac{13}4}=1+\frac1{3+\frac14}$$

The last but one convergent of $\frac{17}{13}$ is $1+\frac13=\frac43$

Using the relationship of the successive convergents of a continued fraction, $17\cdot3-13\cdot4=-1\implies 13\cdot4\equiv1\pmod{17}\implies x\equiv4\pmod{17}$

- Why there is no continuous argument function on $\mathbb{C}\setminus\{0\}$?
- The error term in Taylor series and convolution.
- 2 is a primitive root mod $3^h$ for any positive integer $h$
- Relationship between Binomial and Bernoulli?
- Is there a way to determine how many digits a power of 2 will contain?
- What is the most efficient method to evaluate this indefinite integral?
- Surreal numbers without the axiom of infinity
- Solutions of $f(x)\cdot f(y)=f(x\cdot y)$
- proving of Integral $\int_{0}^{\infty}\frac{e^{-bx}-e^{-ax}}{x}dx = \ln\left(\frac{a}{b}\right)$
- Smallest closed ball enclosing a compact set
- Derivation of mean and variance of Hypergeometric Distribution
- What is special about simplices, circles, paths and cubes?
- Calculating Distance of a Point from an Ellipse Border
- A basis for the dual space of $V$
- Variance of the number of empty cells