Question on the Euclidean Algorithm

[Kindayr]

Homework Statement

Let a,b\in\mathbb{Z}. Suppose r_{0}=a and r_{1}=b. By the algorithm, r_{i}=0 for some i\geq 2 is the first remainder that terminates. Show that r_{i-1}=\gcd(a,b).

Homework Equations

The Attempt at a Solution

I've shown that c|r_{i-1}, and I know that I should show that r_{i-1}|a and r_{i-1}|b. I just don't know how to show both the latter. I don't know where to continue.

I don't want full solutions just given to me (obviously), just some insight :)

Thanks!

 

[micromass]

Maybe prove first that if a certain c divides r_k and r_{k+1}, then it divides r_{k-1}.
Then apply this result for c=gcd(a,b).

 

[Kindayr]

Nevermind, I got it without having to break it down into cases!

Note, \gcd(a,b)=\gcd(a+mb,b) for any m\in\mathbb{Z}.

Define P(n): \gcd(a_{n-1},a_{n})=\gcd(a_{n},a_{n+1}). Let n_{0}=1 be our base case. Since a_{0}=ma_{1}+a_{2} by the division algorithm, we have \gcd(a_{0},a_{1})=\gcd(ma_{1}+a_{2})=\gcd(ma_{1}-ma_{1}+a_{2},a_{1})=\gcd(a_{2},a_{1})=\gcd(a_{1},a_{2}), thus P(n_{0}) is true.

Now let n\geq 1 such that P(n) is true. Then we have \gcd(a_{n-1},a_{n})=\gcd(a_{n},a_{n+1})=\gcd(ma_{n+1}+a_{n+2},a_{n+1})=\gcd(ma_{n+1}-ma_{n+1}+a_{n+2},a_{n+1})=\gcd(a_{n+2},a_{n+1})=\gcd(a_{n+1},a_{n+2}). Hence, \gcd(a_{n},a_{n+1})=\gcd(a_{n+1},a_{n+2}), thus for all n\geq 1, P(n)\implies P(n+1). Hence, by the principle of Mathematical Induction: \forall n\geq 1,P(n).

Since we know that for some i, a_{i}=0, it follows that: \gcd(a,b)=\gcd(a_{0},a_{1})=\cdots =\gcd(a_{i-1},a_{i})=\gcd(a_{i-1},0)=a_{i-1}. Therefore, \gcd(a,b)=a_{i-1}, as required.