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 3 of 5: Three values that mutually control each other's difference

Previous step Next step

In plain words

Feeding the three pairs (x,y), (x,x-y) and (y,y-x) into the hypothesis, and using that f ignores sign, shows f(x), f(y) and f(x-y) each divide the difference of the other two.

f(x-y)\mid f(x)-f(y),\ \ f(y)\mid f(x)-f(x-y),\ \ f(x)\mid f(y)-f(x-y)

Detailed analysis

For any integers $x,y$ : taking $m=x,n=y$ in the hypothesis gives $f(x-y)\mid f(x)-f(y)$ directly. Taking $m=x,n=x-y$ gives $f(y)\mid f(x)-f(x-y)$ . Taking $m=y,n=y-x$ gives $f(x)\mid f(y)-f(y-x)$ , and since $f(y-x)=f(x-y)$ by the previous step this reads $f(x)\mid f(y)-f(x-y)$ . Altogether, $f(x-y)\mid f(x)-f(y),\ \ f(y)\mid f(x)-f(x-y),\ \ f(x)\mid f(y)-f(x-y)$ .