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 B ́ezout coefficients and the inverse of the modulo. [Hint: Example 2 of section 4.4 in the book]

(a) - (3 points) 678 modulo 2970

(b) - (3 points) 137 modulo 2350

Answer 1

Solution

According to, Euclidean Algorithm, the inverse of a mod b exists, if and only if

$g.c.d {\color{Red} (a, b)} = 1$

Here g.c.d stands for the greatest common divisor.

Solution (a)

To check the inverse for 678 modulo 2970 exists or not, we can write

$2978 = 678 × 4 + 258\\ 678 = 258 × 2 + 162\\ 258 = 162 × 1 + 96\\ 162 = 96 × 1 = 66\\ 96 = 66 × 1 + 30\\ 66 = 30 × 2 + 6 \\ 30 = 6 × 5 + 0 \\$

Hence $g.c.d (2978, 678) = 6 ≠ 1$

Therefore, the inverse of 678 modulo 2970 does not exist.  

Solution (a)

To check the inverse for 137 modulo 2350 exists or not, we can write

$2350 = 137 × 17 + 21\\ 137 = 21 × 6 + 11\\ 21 = 11 × 1 + 10\\ 11 = 10 × 1 + 1 \\$

Hence $g.c.d (2350, 137) = 1$

Therefore, an inverse of 137 modulo 2350 exists.  

Now to find the inverse we proceed as follows.

$11 + 10 (– 1) = 1\\ 21 + 11 (– 1) = 10\\ 137 + 21 (– 6) = 11\\ 2350 + 137 (– 17) = 21$

Therefore,

$11 + (21 + 11 (– 1)) (– 1) = 1\\ 11 – 21 + 11 = 1 \\ 11 × 2 + 21 (-1) = 1$

Then

$(137 + 21 (-6)) × 2 + 21 (-1) = 1\\ 137 × 2 + 21 × (-13) = 1$

 

And finally

$137 × 2 + (2350 + 137 × (-17))(-13) =1 \\ 2350 × 2(-13) + 137 × 2(223) = 1$

Hence Bezout coefficients are (-13) and (223)

 

And the invers of 137 modulo 2350 is $223$