derive the eculidean algorithm for calculating gcd(a,b)

Question

I already prove that if a=bq+r for some non-negative number r then gcd(a,b)=gcd(b,r), and could anyone tell me how it can be used to derive the eculidean algorithm for calculating gcd(a,b)?

Answer 1

• Start with $a=bq_0+r_1$, with $0\leq r_1<b$.

• Now write $b=r_1q_1+r_2$, with $0\leq r_2<r_1$;

• now write $r_1=r_2q_2+r_3$, with $0\leq r_3<r_2$;

• keep going.

As the remainders are decreasing on each step, after a finite number of steps you get $r_{n+1}=0$, so the last equality is $r_{n-1}=r_nq_n$.

Now $$ (a,b)=(b,r_1)=(r_1,r_2)=\cdots=(r_{n-1},r_n)=r_n. $$ The last equality due to the fact that $r_n$ divides $r_{n-1}$.

Answer 2

What you have there is exactly one step in the Euclidean algorithm. You just repeat it until you reach $r=0$. You have already shown that the $\gcd$ doesn't change when you do it one step, so it won't change when you do it one more, and one more, and so on.

The only real thing left to prove is that you can actually always reach the point where $r=0$ with finitely many repetitions.