Let a 102 and b 83 a Prove that gcda b 1 using the Euclid

Let a = 102 and b = 83.

(a) Prove that gcd(a, b) = 1 using the Euclidean algorithm.

(b) Find integers s and t so that as + bt = 1.

(c) Consider now that 83 Z102. Prove that 83 U(102) by producing the multi-
plicative inverse 83^ 1 as an element from the set {0, 1, 2, . . . , 101}.

Solution

a)

WE use Euclidean algorithm to prove this

102=83+19 ,19= 102-83

83=19*4+7 ,7 =83-19*4=5*83-4*102

19=7*3-2    , 2=7*3-19=15*83-12*102-102+83=16*83-13*102

7=2*3+1    , 1=7-2*3 = 5*83-4*102-48*83+39*102=-43*83+35*102

Hence,

35*102-43*83=1

Hence, gcd(a,b)=1

b)

From part a) we found:35*102-43*83=1

Hence,

s=35,t=-43

c)

35*102-43*83=1

So,

35*102-43*83=0-43*83 =1 mod 102

So,

83^{-1}=-43=-43+102=59

Hence,

83^{-1}=59