- #1

- 161

- 0

## Homework Statement

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].

## Homework Equations

## 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!