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

Please give me some ideas. Thank you.
 A: 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$$
A: @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.
A: 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: 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}$.
A: $\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.
A: $$\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}$
A: Solving $13x \equiv 1 ~ (\text{mod} ~ 17)$ means there is a smallest positive integer $q$ such that we can write
$\tag 1 13q = 1 + 17k \quad \text{ for some integer } k$
But then $4k \equiv 12 ~ (\text{mod} ~ 13)$ and $k \in \{3, 16, 29, \dots\}$.
So we'll just go thru the list $[1+17\times3,1+17\times 16,\dots]$ checking for the first number divisible by $13$.
$\quad 1 + 17 \times 3 = 52 = 4 \times 13$
Well that was easy!
$\tag{ANS} 13 \times 4 \equiv 1 ~ (\text{mod} ~ 17)$
