For the following pairs of integers a b use the Euclidean Al

For the following pairs of integers (a, b), use the Euclidean Algorithm to find gcd (a, b) and s, t element Z such that gcd(a, b) = sa + tb You must show your work to receive credit. (755, 15) (312, 23) (825, 315) (858, 232)

Solution

1. Find the GCD of 755, 15 by Euclidean algorithm:

then 755 = 50*15 + 5

       15 = 3*5 + 0

Thus greatest common divisor of 755 and 15 is 5.

2. Find the GCD of 312, 23 by Euclidean algorithm:

then 312 = 13*23 + 13

       23 = 1*13 + 10

      13 = 1*10 + 3

      10 = 3*3 + 1

        3 = 3*1 + 0

Thus greatest common divisor of 312 and 23 is 1.