You know this (*): For any such that , and .

Note that if divides both and , then divides , since .

Let .

Keep doing that (*) and track the results (keep getting values and in what follows):

. Have .

. Have .

. Have .

. Have .

Etc.

At each stage after the first couple, get that .

But must terminate, either some or some .

Now consider both those cases:

Case:If occurs, then from ,

had that divided . But then divides .

And then divides and . so it divides .

This continues with dividing all the 's on up until eventually dividing both and .

Thus divides .

But also, , so divides .

Therefore, .

Have shown that if , then .

Case:Now suppose that for some n.

Then from , it follows immediately that (and note that gives ).

Thus, when this prrocess terminates, whether it terminates with or , either way, will have some m such that:

and will have produced integers and such that .