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:


Without the aid of a computer or calculating device, find integers x, y, and z such that 35x + 55y + 77z = 1.

Explanation / Answer

remainder[1] := f(x) remainder[2] := a(x) auxiliary[1] := 0 auxiliary[2] := 1 i := 2 while remainder[i] > 1 i := i + 1 remainder[i] := remainder(remainder[i-2] / remainder[i-1]) quotient[i] := quotient(remainder[i-2] / remainder[i-1]) auxiliary[i] := -quotient[i] * auxiliary[i-1] + auxiliary[i-2] inverse := auxiliary[i]

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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