Answer to Question #97684 in Combinatorics | Number Theory for Ibrar Hussain Shah

Question

Calculate GCD(8,35) using EA (Euclid's Algorithm) and calculate the multiplicative inverse of 8 E Z3,, if it exists Also try the same for 21 E Z35.

Answer 1

35 = 4*8 +3 => 3 = 35-4*8

8 =2*3 +2 =>2 = 8 -2*3

3 = 1*2 +1 => 1=3-1*2

2= 2*1 + 0 stop

Plugging back upwards we get:

1= 3 - 1*2 = 3 - (8 -2 *3) = 3*3 - 8 =3*(35-4*8) - 8 = 3*35 -13*8

Therefore 1= 3*35 - 13*8 and GCD(35,8)=1 because 1 is the last non-zero remainder.

Since 1 = 3*35 - 13*8 => 1 = (3*35-13*8) (mod 35) => 1= (-13)*8 (mod 35) => 8^-1 = (-13) (mod 35)

But -13 (mod 35) = (35-13) (mod 35) = 22 (mod 35), so the inverse of 8 modulo 35 is 22.

However, 21 does not have an inverse modulo 35 because GCD(21,35) = 7, thus 21 and 35 are not co-prime.