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 5 of 5: Apply the lemma to f(m), f(n), f(n-m)

Previous step Next step

In plain words

Whichever of the three values turns out to be largest, the lemma always identifies the two smaller ones with each other, and since f(m) is one of the two smallest by hypothesis, it ends up dividing f(n) in every possible arrangement.

f(m)\mid f(n)

Detailed analysis

Suppose $f(m)\le f(n)$ . Apply step 3 with $x=n,y=m$ to the triple $a'=f(n),b'=f(m),c'=f(n-m)$ , which satisfies the three relations of step 3, hence (after reordering by size) the lemma of step 4. Since $f(m)\le f(n)$ , $f(m)$ is never the largest of the three, so it is always one of the two values the lemma identifies as equal; the lemma then says this common value divides the largest of the three. If $f(n)$ is the largest, the lemma gives $f(m)\mid f(n)$ directly. If $f(n-m)$ is the largest instead, the lemma forces $f(m)$ to equal whichever of $f(n),f(n-m)$ is not largest, and since $f(m)\le f(n)\le f(n-m)$ in that case, it forces $f(m)=f(n)$ , which again gives $f(m)\mid f(n)$ . Either way, $f(m)\mid f(n)$ .