(Solved): (a) Using the Euclidean algorithm, find the greatest common divisor of a= 197070 and b=17739, and e ...

(a) Using the Euclidean algorithm, find the greatest common divisor of $a=$ 197070 and $b=17739$, and express the greatest common divisor in the form $ma+nb$ with $m,n?\mathbb{Z}$. (For your own benefit, you should check your answers to be confident that you have not made any mistakes. At the very least, if $d$ is the number you found for the greatest common divisor, you should verify that $d$ divides $a$ and $b$ and that your claimed equality $d=ma+nb$ really does hold.) (b) Show by counterexample that if $c,d,r,s$ are integers such that $rc+sd=$ 5 , then $\gcd (c,d)$ need not be equal to 5 .