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
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$.
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
09.11.2023 12:30