Question

Using the extended Euclidean algorithm, find the multiplicative inverse of a. 1234 mod 4321 b. 24140 mod 40902

Answer 1

(a) The inverse of 1234 (mod 4321) is x such that 1234*x ≡ 1 (mod 4321). Apply Euclid's algorithm:

4321 = 1234 * 3 + 619

1234 = 619 * 1 + 615

619 = 615 * 1 + 4

615 = 4 * 153 + 3

4 = 3 * 1 + 1

Now write 1 as a linear combination of 4321 and 1234:

1 = 4 - 3

1 = 4 - (615 - 4 * 153) = 4 * 154 - 615

1 = 619 * 154 - 155 * (1234 - 619) = 619 * 309 - 155 * 1234

1 = (4321 - 1234 * 3) * 309 - 155 * 1234 = 4321 * 309 - 1082 * 1234

Reducing this leaves us with

1 ≡ -1082 * 1234 (mod 4321)

and so the inverse is

-1082 ≡ 3239 (mod 4321)

(b) Both 24140 and 40902 are even, so there GCD can't possibly be 1 and there is no inverse.