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:

A. Solve the congruence: 15x = 56 (mod 101).
B. Without the aid of a computer or calculating device, find integers x, y, and z such that 35x + 55y + 77z = 1.

Explanation / Answer

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: A. Solve the congruence: 15x = 56 (mod 101). B. Without the aid of a computer or calculating device, find integers x, y, and z such that 35x + 55y + 77z = 1.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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