Find all $f:\mathbb{N}\to\mathbb{N}$ satisfying that for all $m,n\in\mathbb{N}$, the nonnegative integer $|f(m+n)-f(m)|$ is a divisor of $f(n)$. Proposed by usjl
Problem
Source: 2023 Taiwan TST Round 1 Mock Exam P5
Tags: number theory, Taiwan
11.07.2023 18:27
This was proposed to 2022 IMO but sadly did not make to ISL. I am a bit disappointed after seeing how whack the N section of 2022 ISL is :/
11.07.2023 19:07
Since $0$ is not a divisor of any positive integer we get that $f(m+n)\neq f(m)$ so $f$ is injective. Now, for $m=1$: $f(n+1)-f(1)|f(n)$ $n=1$: $f(m+1)-f(m)|f(1)$ Take $n>N$ such that $f(n+1)>f(1)$, then $f(n)=k(f(n+1)-f(1)$ for some positive integer $k$, then $f(1)\geq |f(n+1)-f(n)|=|k(f(n+1)-f(1))-f(n+1)|\geq f(n+1)(k-1)-kf(1)$ so $k=1$ for large enough $n$. Hence $f(n+1)=f(n)+f(1)$ for large $n\Rightarrow f(n)=nf(1)+C,n>N$ Put $m,n>N$ in the condition to get $nf(1)|nf(1)+C\rightarrow C=0$ since $C$ has infinitely many divisors. Now for $n>N$ we have $(m+n)f(1)-f(m)|nf(1)\Rightarrow (m+n)f(1)-f(m)|f(1)m-f(m)\Rightarrow f(n)=f(1)n$ for every $n$ which works,
11.07.2023 19:36
USJL wrote: I am a bit disappointed after seeing how whack the N section of 2022 ISL is :/
11.07.2023 19:44
Solved with dragoon. The answer is $\boxed{f(x) = cx}$ for any positive integer $c$. These work. Now we prove they are the only solutions. Let $P(m,n)$ denote the assertion that \[ f(m+n) - f(m) \mid f(n)\] $P(m,1): f(m+1) - f(m) \mid f(1)$. $P(1,m): f(m+1) - f(1) \mid f(m)$. For $a>b$, $P(b, a-b): f(a) - f(b) \mid f(a-b)$. Call a pair $(a,b)$ good with $a>b$ if $f(1) \mid f(a) - f(b)$. Claim: Over all good pairs $(a,b)$, there are infinitely many possible values of $a-b$. Proof: By Pigeonhole, any set with $f(1) + 1$ elements has a good pair. Consider the sets \[\{1,2,\ldots, f(1) + 1)\}, \{N,2N, \ldots, f(1) + 1)N\} , \{N^2,2N^2, \ldots (f(1) +1) N^2\},\ldots \]more generally the sets of the form $\{N^k , 2N^k , \ldots, (f(1) + 1) N^k\}$ for any nonnegative integer $k$, where $N$ is a sufficiently large positive integer. The sets of the $\binom{f(1) + 1}{2} $ differences in each set are disjoint. Since there are infinitely many sets with $f(1) + 1$ elements, we have infinitely many good pairs with pairwise distinct values of $a-b$, hence infinitely many values of $a-b$ over good pairs $(a,b)$. $\square$ Notice for a good pair, we have $f(1) \mid f(a) - f(b) \mid f(a-b)$, so there are infinitely many $c$ with $f(1)\mid f(c)$ (1) Claim: If $f(1) \mid f(x)$, then $f(1)\mid f(x-1)$. Proof: $P(1,x-1): f(x) - f(1)\mid f(x-1)$. Since $f(1)\mid f(x) - f(1)$, we have $f(1) \mid f(x-1)$. $\square$ Repeatedly applying this claim, we get $f(1)\mid f(x-n)$ for any positive integer $n<x$. Claim: $f(1)\mid f(k) $ for all $k\in \mathbb{N}$. Proof: Choose some $x>k$ such that $f(1)\mid f(x)$ (we know such an $x$ exists by (1)). Then we have $f(1) \mid f(x - (x-k)) = f(k)$, as desired. $\square$ Now, $P(m,1)$ gives that $f(m+1) - f(m) \mid f(1)$, but we know that $f(1)$ divides $f(m+1)$ and $f(m)$, so it divides their difference also. Hence $f(m+1) - f(m) = f(1)$ for each $m$. From here it's easy to see that $f(n) =n f(1)$ for all positive integers $n$, which corresponds to the solutions described above.
16.12.2023 12:24
In the following solution, we will omit the absolute value signs, since it doesn't make much of a difference and gets mixed up with divisibility signs. We claim that $\boxed{f(x) = cx}$ for any positive integer $c$. These suffice, and we now prove that these are the solutions. Firstly, if $f(x) = f(y)$, then WLOG $x> y$. In this case, plugging $P(y, x - y)$ results in a contradiction, hence injectivity holds. By pigeonhole we know that there exists an infinite set $A_i$ such that $\forall$ $x \in A_i$, \[f(x)\equiv i\pmod{f(1)}\]Hence, we can find $a, b\in A_i$ which are arbitrarily apart, then (WLOG $b > a$) $P(a, b - a):$ $f(1) | f(b) - f(a) | f(b - a)$ means there exists arbitrarily large $k$ such that $f(1) | f(k)$. $P(1, k - 1): f(1) | f(k) - f(1) | f(k - 1)$ $P(1, k - 2): f(1) | f(k - 1) - f(1) | f(k - 2)$ We can repeat this procedure, thereby proving $f(1) | f(x)$ for all $x\in \mathbb{N}$. Since $f(2) - f(1) | f(1)$, hence $f(2) = 2f(1)$. Since $f(3) - f(2) | f(1)$, hence by injectivity $f(3) = 3f(1)$. Applying this procedure arbitrarily many times, we get that $\boxed{f(x) = xf(1)}$ $\forall x \in \mathbb{N}$, proving what we had claimed earlier.