1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Integers on the board

  1. Nov 17, 2007 #1
    1. The problem statement, all variables and given/known data

    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. jcsd
  3. Nov 18, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Nov 18, 2007 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook