Find all functions $f : N \to N$ such that $f(p)$ divides $f(n)^p -n$ by any natural number $n$ and prime number $p$.
Problem
Source: IFYM - XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade,finals p5
Tags: algebra, divides
13.11.2022 12:32
Plug $n\mapsto p$ to get $f(p)\mid f(p)^p-p\implies f(p)\mid p\implies f(p)=1,p$. Case 1: There is infinitely many $p$ such that $f(p)=p$. Take such $p$ to get $p\mid f(n)^p-n\implies p\mid f(n)-n$. Then take such $p$ large enough to get $f(n)=n$ for all positive integers $n$. Case 2: There is finitely many $p$ such that $f(p)=p$ (but there still exists such $p$.) Let them be $p_1<p_2<\dots<p_k$. The rest of prime will give $f(p)=1$. Plug $p\mapsto p_i$ to get $f(n)\equiv n\pmod{p_i}$ for all positive integers $n$. Then take $n\mapsto p$ where $p$ is any prime greater than $p_k$. We have $1\equiv p\pmod{p_i}$. But if $p_i\neq 2$ then by dirichlet's there exists prime $p$ large enough that $p\equiv 2\pmod{p_i}$. So $p_i=2$ which means that $f(2)=2$, $k=1$ and so $f(p)=1$ for all odd prime. Plug $n\mapsto 2$ to get $2\mid f(n)-n\implies f(n)$ has the same parity as $n$. Case 3: $f(p)=1$ for all prime $p$. Note that $f(n)$ where $n\neq \text{prime}$ can be anything. We conclude that $f(n)=n$ for all positive integers $n$. $f(2)=2, f(p)=1$ for odd prime $p$, and $f(n)$ can be anything that has the same parity as $n$ for $n$ that is not prime. $f(p)=1$ for prime $p$, and $f(n)$ can be anything for $n$ that is not prime. All of these obviously work. EDIT: Fix silly mistake in case 2. Thanks @below for pointing out.
13.11.2022 20:46
Not exactly, how about the following f: $f(2)=2$, $f(p)=1$ for all $p>2$ prime and $f(n)\equiv n\pmod{n}$ for any $n$. Clearly this satisfies the conditions. So, fix Case 2 above.