48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Suppose that function $f:\mathbb{N}\to \mathbb{N}$ satisfies the problem conditions.

Lemma. For any prime $p$ and any $x,y\in \mathbb{N}$, we have $x\equiv y(\mathrm{mod}p)$ if and only if $f(x)\equiv f(y)(\mathrm{mod}p)$. Moreover, $p\mid f(x)$ if and only if $p\mid x$.

Proof. Consider an arbitrary prime $p$. Since $f$ is surjective, there exists some $x\in \mathbb{N}$ such that $p\mid f(x)$. Let $$d=\min \{x\in \mathbb{N}:p\mid f(x)\}$$ By induction on $k$, we obtain that $p\mid f(kd)$ for all $k\in \mathbb{N}$. The base is true since $p\mid f(d)$. Moreover, if $p\mid f(kd)$ and $p\mid f(d)$ then, by the problem condition, $p\mid f(kd+d)=f((k+1)d)$ as required.

Suppose that there exists an $x\in \mathbb{N}$ such that $d\nmid x$ but $p\mid f(x)$. Let $$y=\min \{x\in \mathbb{N}:d\nmid x,p\mid f(x)\}.$$ By the choice of $d$, we have $y>d$, and $y-d$ is a positive integer not divisible by $d$. Then $p\nmid f(y-d)$, while $p\mid f(d)$ and $p\mid f(d+(y-d))=f(y)$. This contradicts the problem condition. Hence, there is no such $x$, and $$\begin{array}{c}p\mid f(x)⟺d\mid x.\end{array}\text{\hspace{1em}(1)}$$ Take arbitrary $x,y\in \mathbb{N}$ such that $x\equiv y(\mathrm{mod}d)$. We have $p\mid f(x+(2xd-x))=f(2xd)$; moreover, since $d\mid 2xd+(y-x)=y+(2xd-x)$, we get $p\mid f(y+(2xd-x))$. Then by the problem condition $p\mid f(x)+f(2xd-x)$, $p\mid f(y)+f(2xd-x)$, and hence $f(x)\equiv -f(2xd-x)\equiv f(y)(\mathrm{mod}p)$.

On the other hand, assume that $f(x)\equiv f(y)(\mathrm{mod}p)$. Again we have $p\mid f(x)+f(2xd-x)$ which by our assumption implies that $p\mid f(x)+f(2xd-x)+(f(y)-f(x))=f(y)+f(2xd-x)$. Hence by the problem condition $p\mid f(y+(2xd-x))$. Using (1) we get $0\equiv y+(2xd-x)\equiv y-x(\mathrm{mod}d)$.

Thus, we have proved that $$\begin{array}{c}x\equiv y(\mathrm{mod}d)⟺f(x)\equiv f(y)(\mathrm{mod}p).\end{array}\text{\hspace{1em}(2)}$$ We are left to show that $p=d$: in this case (1) and (2) provide the desired statements.

The numbers $1,2,\dots ,d$ have distinct residues modulo $d$. By (2), numbers $f(1),f(2),\dots ,f(d)$ have distinct residues modulo $p$; hence there are at least $d$ distinct residues, and $p\ge d$. On the other hand, by the surjectivity of $f$, there exist $x_1,\dots ,x_p\in \mathbb{N}$ such that $f(x_i)=i$ for any $i=1,2,\dots ,p$. By (2), all these $x_i$'s have distinct residues modulo $d$. For the same reasons, $d\ge p$. Hence, $d=p$.

Now we prove that $f(n)=n$ by induction on $n$. If $n=1$ then, by the Lemma, $p\nmid f(1)$ for any prime $p$, so $f(1)=1$, and the base is established. Suppose that $n>1$ and denote $k=f(n)$. Note that there exists a prime $q\mid n$, so by the Lemma $q\mid k$ and $k>1$.

If $k>n$ then $k-n+1>1$, and there exists a prime $p\mid k-n+1$; we have $k\equiv n-1(\mathrm{mod}p)$. By the induction hypothesis we have $f(n-1)=n-1\equiv k=f(n)(\mathrm{mod}p)$. Now, by the Lemma we obtain $n-1\equiv n(\mathrm{mod}p)$ which cannot be true.

Analogously, if $k<n$, then $f(k-1)=k-1$ by induction hypothesis. Moreover, $n-k+1>1$, so there exists a prime $p\mid n-k+1$ and $n\equiv k-1(\mathrm{mod}p)$. By the Lemma again, $k=f(n)\equiv f(k-1)=k-1(\mathrm{mod}p)$, which is also false. The only remaining case is $k=n$, so $f(n)=n$.

Finally, the function $f(n)=n$ obviously satisfies the condition.