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.

Solutions Collecting From Web of "How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $?"

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}$