1. Not finding help here? Sign up for a free 30min 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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Integers on the board
  1. Diving board (Replies: 26)

  2. Division of integers (Replies: 5)

  3. Function on Integers (Replies: 3)

  4. Integer sequence (Replies: 6)