## Answers

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.

.

Dear Friend

here is a simple code for it using recursion

int gcd(int a, int b) {

return (b == 0) ? a : gcd(b, a % b);

}

and this site will help u if u want more

http://en.literateprograms.org/Euclidean_algorithm_%28C%29.