Competition problem — Number theory

Library / /42 of 520

Number theory Difficulty 5.3 AIME, harder Prove it

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, n$ with $f(m) \leq f(n)$ the number $f(n)$ is divisible by $f(m)$ .

Solution

Suppose that $x$ and $y$ are two integers with $f(x)0$ $so$ f(x-y) \leq f(y)-f(x)<f(y) $. Hence the number$ d=f(x)-f(x-y) $satisfies$ $-f(y)<-f(x-y)<d<f(x)<f(y) .$ $Taking$ m=x $and$ n=x-y $we see that$ f(y) \mid d $, so we deduce$ d=0 $, or in other words$ f(x)=f(x-y) $. Taking$ m=x $and$ n=y $we see that$ f(x)=f(x-y) \mid f(x)-f(y) $, which implies$ f(x) \mid f(y)$.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.