6. Let a=315,b=825.

(a) Use the Euclidean algorithm to find the greatest common divisor of the pair

of integers a, b. (5 points)

To find the greatest common divisor (god) of a=315 and b=825 using the Euclidean algorithm, we perform the following steps:

825 = 2 315 + 195

315 = 1 195 120

195 = 1 120 + 75

120 = 1 75 45

75 = 1 45 30

45 = 1 30 + 15

30 = 2 15 + 0

Since the remainder is 0, the algorithm terminates, and the last nonzero remainder is 15. Therefore, the god of 315 and 825 is 15

(b) Find integers s and t such that sa + tb =gcd(a, b). (5 points)

7 Let n=100,=243. Show that gcd (n,)=1, and find the inverses of n the modulo satisfying 0 < s < . (10 points)