Find all functions $f: \mathbb{N} \rightarrow \mathbb {N}$ such that for all positive integers $m, n$, $f(m+n)\mid f(m)+f(n)$ and $f(m)f(n) \mid f(mn)$.
Problem
Source: Mexico 2023/6
Tags: number theory
melowmolly
08.11.2023 12:57
$f(1)^2|f(1)\Rightarrow f(1)=1$. $f(2)|2f(1)=2$. If $f(2)=2$: $f(3)|3, f(4)|2f(2)=4, 4=f(2)^2|f(4)\Rightarrow f(4)=4, f(4)|f(1)+f(3)\Rightarrow 4|1+f(3)\Rightarrow f(3)=3$. We now prove by induction that $f(x)=x$ . Assume that $f(x)=x \forall x \le 2n$. We have $f(2n+2)|2f(n+1),f(n+1)f(2)|f(2n+2)\Rightarrow 2f(n+1)|f(2n+2)\Rightarrow f(2n+2)=2n+2, 2n+2|f(2n+1)+1\Rightarrow f(2n+1)\ge 2n+1, f(2n+1)|f(2n)+1=2n+1\Rightarrow f(2n+1)\le 2n+1\Rightarrow f(2n+1)=2n+1$. If $f(2)=1$: Assume $\forall x \le n$ then $f(x)=1$. Obviously we have $f(n+1)|f(n)+f(1)=2$. If $f(n+1)=2$: $f(n+2)|f(n)+f(2)=2,f(n+2)|f(n+1)+f(1)=3\Rightarrow f(n+2)=1$ $f(n+3)|f(n+1)+f(2)=3,f(n+3)|f(n+2)+f(1)=2\Rightarrow f(n+3)=1$ $\cdots$ $f(2n+1)|f(n+1)+f(n)=3,f(2n+1)|f(2n)+f(1)=2\Rightarrow f(2n+1)=1$ $f(2n+2)|f(2n+1)+f(1)=2,f(2)f(n+1)|f(2n+2)\Rightarrow f(2n+2)=2$ $f(2n+3)|f(2n+1)+f(2)=2, f(2n+3)|f(2n+2)+f(1)=3\Rightarrow f(2n+3)=1$ $\cdots$ $4=f(n+1)^2|f(n^2+2n+1),f(n^2+2n+1)|f(n^2+2n)+f(1)=2$ which is a contradiction. So $f(x)\equiv x$ or $f(x)\equiv 1$.
rama1728
08.11.2023 13:20
Lol what? This problem is exactly GGHX's SEIF 2022 N1 Looks like SEIF's problems are capable enough to appear on the IMO, considering that an N1 appeared as Mexico's NMO P6
VicKmath7
09.11.2023 12:30
Firstly, $f(1)^2 \mid f(1)$, so $f(1)=1$. Hence, $f(m)\leq f(m-1)+1$ and by induction $f(m) \leq m$. Moreover, we have $f(2)f(n) \mid f(2n) \mid 2f(n)$, so $f(2) \mid 2$, i.e. $f(2)=1$ or $f(2)=2$.
$\textbf{Case 1.}$ Suppose that $f(2)=2$. It is easy to see that by induction $2^e \mid f(2^e) \leq 2^e$, so $f(2^e)=2^e$ for all positive integers $e$. For any fixed $m$, take a $e$ such that $2^e>m$; then, $2^e=f(2^e)\mid f(2^e-m)+f(m) \leq 2^e$, so equality holds everywhere and thus $f(m)=m$, so the identity function is the only solution here.
$\textbf{Case 2.}$ Suppose that $f(2)=1$ and suppose FTSoC that $f$ is not the constant $1$. Take the minimal $m$, such that $f(m) \geq 2$; we have $f(m) \mid f(m-1)+f(1)=2$, so $f(m)=2$. It is easy to see that $2 \mid f(km)$ for all positive integers $k$.
We actually claim something stronger: $f(n)=1$ for $m \nmid n$ and $f(n)=2$ for $m \mid n$. Since $f(1)=f(2)=1$, $f(n) \mid f(n-1)-f(n-2)$, which implies that $f(m+1) \mid f(m)-f(m-1)=1$, so $f(m+1)=1$. Now, for any positive integer $2 \leq r<m$, we have $f(m+r)\mid f(m)+f(r)=3$ and $f(m+r) \mid f(m-1)+f(r+1)=2$, so $f(m+r)=1$. By generalizing this, we can easily prove our claim by strong induction.
Now, if $m^2 \mid n$, then $4 \mid f(n)$, which is a contradiction since all values the function attains are $1,2$.