Answer to Question #306251 in Discrete Mathematics for Frank

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$