# Harrison Chapman

## Math 301: The Euclidean Algorithm

Class date: Friday, October 11, 2019
1. First, let’s prove why the Euclidean Algorithm works!

1. Show that $$\gcd(a,b) = \gcd(a, b-a)$$:

1. Let $$d = \gcd(a,b)$$ and $$d’ = \gcd(a, b-a)$$

2. Show that $$d’ \mid b$$ and $$d \mid (b-a)$$.

3. Explain why $$d’ \le d$$ and $$d \le d’$$.

4. Conclude that $$d’ = d$$

2. Show our Fact, that $$\gcd(a,b) = \gcd(a,r)$$ by applying part (a) repeatedly.

2. Find integers $$m, n$$ so that $$\gcd(102, 38) = m102 + n38$$.