Problem 5

Let

f

be a function from the set of integers to the set of positive integers. Suppose that, for any two integers

m

and

n

, the difference

f(m)-f(n)

is divisible by

f(m-n)

. Prove that, for all integers

m

and

n

with

f(m)\le f(n)

, the number

f(n)

is divisible by

f(m)

Step 4 of 5: A squeeze lemma for such triples

Previous step Next step

In plain words

Order the three values from largest to smallest; the largest divides the gap between the other two, but that gap is too small to be anything but zero, so the two smaller values collapse into one, which then plainly divides the largest.

b=c\ \text{and}\ b\mid a

Detailed analysis

Suppose positive integers $a,b,c$ satisfy $c\mid a-b$ , $b\mid a-c$ and $a\mid b-c$ , and order them so $a\ge b\ge c>0$ . Then $0\le b-c<a$ (since $b\le a$ and $c>0$ ), and $a\mid b-c$ forces $b-c=0$ , i.e. $b=c$ . Substituting into $b\mid a-c$ gives $b\mid a-b$ , hence $b\mid a$ . So $b=c\ \text{and}\ b\mid a$ : the two smaller of the three values coincide, and that common value divides the largest.