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 asfollows: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.
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 and auxiliary are the same.
0
