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.

Solution 1:

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

Solution 2:

@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.

Solution 3:

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.