# Homework Help: Integers on the board

1. Nov 17, 2007

### ehrenfest

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. The attempt at a solution

2. Nov 18, 2007

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

3. Nov 18, 2007

### ehrenfest

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.