First, let’s prove why the Euclidean Algorithm works!
Show that \(\gcd(a,b) = \gcd(a, b-a)\):
Let \(d = \gcd(a,b)\) and \(d’ = \gcd(a, b-a)\)
Show that \(d’ \mid b\) and \(d \mid (b-a)\).
Explain why \(d’ \le d\) and \(d \le d’\).
Conclude that \(d’ = d\)
Show our Fact, that \(\gcd(a,b) = \gcd(a,r)\) by applying part (a) repeatedly.
Find integers \(m, n\) so that \(\gcd(102, 38) = m102 + n38\).