elementary number theory - 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.

Answer

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