Answer to Question #250614 in Combinatorics | Number Theory for Alina

Question

Find out if the inverse exists for the following, give reasoning behind your answer. If you conclude that the inverse exists then find the Bezout coefficients and the inverse of the modulo.

(a) 678 modulo 2970

(b) 137 modulo 2350

Answer 1

x is a multiplicative inverse of a modulo m if a * x and 1 are congruent modulo m:

a * x ≡ 1 mod m

For $a\ mod\ m$, the multiplicative modular inverse of a modulo m  exists if and only if a and m are relatively prime.

a)

multiplicative modular inverse does not exist (678 and 2970 have common factor 2)

b)

Bézout's identity:

$137x+2350y=1$

using extended Euclidean Algorithm:

$2350=17\cdot 137+21$

$137=6\cdot 21+11$

$21=1\cdot 11+10$

$11=1\cdot 10+1$

$1=11-1\cdot10=11-1\cdot(21-1\cdot11)=2\cdot11-1\cdot21=2(137-6\cdot21)-1\cdot21=$

$=2\cdot137-13\cdot21=2\cdot137-13(2350-17\cdot137)=223\cdot137-13\cdot2350$

$x=223,\ y=13$

multiplicative inverse:

$x=223$