Proving Total Order of Integers through LCM and GCD Relationship

[ehrenfest]

Homework Statement

http://math.stanford.edu/~vakil/putnam07/07putnam2.pdf

I am working on problem 5.

It is clear that the integers will not change if they can be totally ordered by divisibility, but I need help proving that they will reach such a state. Obviously after every step, the lcm of the two integers will divide the gcd of the two integers you just replacement. But then I am stuck.

Homework Equations

The Attempt at a Solution

 

[morphism]

This is a famous problem. Prove that the sum of all the numbers doesn't decrease after each iteration. Then, because the sum is bounded, ...

Here's a similar problem. The numbers 1,2,...,2n are written on a blackboard, where n is a positive odd integer. At any time, we can choose two of them and replace them with the absolute value of their difference. Prove that an odd number will remain at the end.

 

[ehrenfest]

This is a famous problem. Prove that the sum of all the numbers doesn't decrease after each iteration. Then, because the sum is bounded, ...

Lets say the 2 numbers are a and b. If lcm(a,b) is not equal to a or b, then it must at least twice as large as max(a,b). If lcm(a,b) = a or b then a divides b or b divides a and the numbers are replaced by themselves. Then the sum is bounded by

number of numbers times gcd(all of the numbers)

so we are done.