Notes: Suppose (a, n) = 1, then there is an integer s such that as = 1 (mod n).

Question

Notes: Suppose (a, n) = 1, then there is an integer s such that as = 1 (mod n). This s is called the inverse of a, i.e., a-1 (mod n). The way to find the inverse is as follows:
1) Use the extended Euclidean algorithm to find s and t such that as + nt = 1;
2) Then a-1(mod n) = s.
In the lecture, we gave an example to find 37-1(mod 121) in three steps.
Step-1: use Euclidean algorithm to get the gcd(121, 37) although we knew it’s one.
Step-2: use extended Euclidean algorithm, which is reverse of Euclidean algorithm, to get s and t, such that 37s + 121t = 1. We got s = 36, t = -11, therefore 37-1(mod 121) = 36.
Step-3: verify that 37s = 1 (mod 121). 37×36 = 1332 = 11×121 + 1 = 1 (mod 121), so the congruence 37s = 1 (mod 121) is verified.

Here are the questions for you to solve:

1. Follow the steps described above, find 28-1 (mod 75).

Explanation / Answer

75=2*28+19
73*28mod75=19
28=1*19+9 3*28mod75=9
19=2*9+1 67*28mod75=1
9=9*1 Hence, 28 -1 mod 75 = 67.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.