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.