Find all functions \( f : \mathbb{N} \to \mathbb{N} \) that satisfy the following condition: for any positive integers \( m \) and \( n \) such that \( m > n \) and \( m \) is not divisible by \( n \), if we denote by \( r \) the remainder of the division of \( m \) by \( n \), then the remainder of the division of \( f(m) \) by \( n \) is \( f(r) \). Proposed by Mykyta Kharin
Problem
Source: Kyiv City MO 2025 Round 1, Problem 10.4
Tags: number theory, functional equation
pco
20.01.2025 10:10
MS_Kekas wrote: Find all functions \( f : \mathbb{N} \to \mathbb{N} \) that satisfy the following condition: for any positive integers \( m \) and \( n \) such that \( m > n \) and \( m \) is not divisible by \( n \), if we denote by \( r \) the remainder of the division of \( m \) by \( n \), then the remainder of the division of \( f(m) \) by \( n \) is \( f(r) \). 1) $f(x)\le x$ $\forall x\ge 1$
$2x+1>x+1$ and is not divisible by $x+1$.
Remainder of division of $2x+1$ by $x+1$ is $x$ and so remainder of division of $f(2x+1)$ by $x+1$ is $f(x)$ and so $f(x)<x+1$
Q.E.D.
2) $\forall x\ge 1$, either $f(x)=1$, either $f(x)=x$
So $f(1)=1$ and $f(2)\in\{1,2\}$
Let $x\ge 3$ : $x>x-1$ and is not divisible by $x-1$.
Remainder of division of $x$ by $x-1$ is $1$ and so remainder of division of $f(x)$ by $x-1$ is $f(1)=1$
and so, since $f(x)\le x\le 2(x-1)+1$ : either $f(x)=0\times (x-1)+1=1$, either $f(x)=1\times(x-1)+1=x$
Q.E.D.
3) If $f(x)=1$ for some $x>1$, then $\boxed{\text{S1 : }f(x)=1\quad\forall x\in\mathbb Z_{>0}}$
If $f(x)=1$ for some $x>1$, then :
$2x+1>x+1$ and is not divisible by $x+1$ and so :
Remainder of division of $2x+1$ by $x+1$ is $x$ and so remainder of division of $f(2x+1)$ by $x+1$ is $f(x)=1$
But if $f(2x+1)=2x+1$, then its remainder when divided by $x+1$ is $x$. So $f(2x+1)=1$
And so we can find such $x$ as great as we want.
If $f(x)=1$ for some $x>4$, then let $2\le y<\frac x2$ :
$x>x-y$ and $x-y$ does not divide $x$. So :
Remainder of division of $x$ by $x-y$ is $y$ and so remainder of division of $f(x)=1$ by $x-y$ is $f(y)$ and so $f(y)=1$
So $f(y)=1$ $\forall y\in[2,\frac x2)$
And since we can find such $x$ as great as we want, $f(y)=1$ $\forall y$, which indeed fits
Q.E.D.
4) If $f(x)\ne 1$ $\forall x>1$, then $\boxed{\text{S2 : }f(x)=x\quad\forall x\in\mathbb Z_{>0}}$
This is an immediate consequence of 2) above and $f\equiv Id$ indeed fits.
Q.E.D.