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$$
No comments:
Post a Comment