use the euclidian algorithn to find the gcd of a165 and b357

use the euclidian algorithn to find the gcd of a=165 and b=357, use this calculation to find s and t so that

(a,b) = sa +tb (bezout\'s equation)

Solution

357 =165*2 +27

165 =27*6 +3

27=3*9+0

H C F=3

Now 3= 165-(27*6)

           = 165- (357-165*2)*6

           = 165-357*6+165*12

           =165*13 + 357*(-6)

There fore (165,357) = sa+tb   where s=13 t= -6