(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

2. Relevant equations

3. The attempt at a solution

I've shown that [itex]c|r_{i-1}[/itex], and I know that I should show that [itex]r_{i-1}|a[/itex] and [itex]r_{i-1}|b[/itex]. 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Question on the Euclidean Algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**