SAUDI ARABIAN IMO Booklet 2023

(Base on the solution of Hadi Alaithan, IMO 2023's team member) Note that for $x,y$ are coprime positive integers, we have $$x-y\mid x^{f(x)}-y^{f(y)}\iff x-y\mid x^{|f(x)-f(y)|}-1.$$ Now we state the following lemma: Lemma (Zsigmondy's Theorem): for $a>b\ge 1$ be coprime integers and $n\ge 2$, there exists a prime divisor of $a^n-b^n$ that does not divide $a^k-b^k$ for all $1\le k<n$, except when $n=2$ and $a+b$ is a power of $2$ or $(a,b,n)=(2,1,6)$.

Back to the original problem, for any coprime integers $x$ and $y$, we show that $|f(x)-f(y)|\le 1$. Suppose that the difference is larger than $1$, then there exists a prime $p$ divides $f(x)-f(y)$. Because $x$ and $y$ are relatively prime, one of these numbers is not a multiple of $p$. Assume that $\gcd (x,p)=1$. By choosing a suitable number $z$, we will show that this is a contradiction.

Denote $k=v_p(f(x)-f(y))$. By the lemma, for some $N_1>k$, there exists a prime $q_1$ such that $${\mathrm{ord}}_{q_1}(x)=p^{N_1},q_1>xy.$$ Similarly, for some $N_2>N_1>k$ such that there exists a prime $q_2>q_1$ and $${\mathrm{ord}}_{q_2}(y)=p^{N_2}$$ It is obvious that $q_1,q_2,x$ and $y$ are pairwise relatively prime. By Chinese remainder theorem, there exists a positive integer $z$ such that $$\{\begin{array}{ll}z\equiv 1(\mathrm{mod}x),& z\equiv x(\mathrm{mod}{q}_1),\\ z\equiv 1(\mathrm{mod}y),& z\equiv y(\mathrm{mod}{q}_2).\end{array}$$ These conditions give $$\{\begin{array}{l}{q}_1\mid (z-x)\mid x^{|f(z)-f(x)|}-1\\ q_2\mid (z-y)\mid y^{|f(z)-f(y)|}-1.\end{array}$$ Hence $p^{N_1}\mid f(x)-f(z)$ and $p^{N_2}\mid f(x)-f(y)$. These give $p^{N_1}\mid f(x)-f(y)$. This is a contradiction.

Now, we show that $f(x)=f(y)$ for all coprime $x,y>1$. Choose $z>2x,2y$ such that $\gcd (z,xy)=1$. Then we have $$z-x>x-1,z-y>y-1.$$ Then both $f(z)-f(x)=0$ and $f(z)-f(y)=0$ due to the divisibility. We obtain that $f(x)=f(y)$ if $x$ and $y$ are relatively prime.

In conclusion, $f$ is constant on $\{2,3,\dots \}$ and $f(1)\in \mathbb{N}$.