Find all functions \(f:\mathbb N\to\mathbb N\) such that for all primes \(p\), \(p\mid f(a)^{f(p)}-f(b)^p\iff p\mid a-b\)

Notice that \(p\mid a-b\iff a\equiv b\pmod p\) and by Euler's theorem, \(p\mid f(a)^{f(p)}-f(b)^p\iff f(a)^{f(p)}\equiv f(b)^p\equiv f(b)\pmod p\).

This must hold true when \(a=b\), and therefore we get that \(f(a)^{f(p)}\equiv f(a)\pmod p\) for all \(a\). This holds only for a limited number of functions:

1. \(f(x)=x\), and we can easily check that \(f(a)^{f(p)}=a^p\equiv a\equiv b=f(b)\pmod p\) which fulfills the above conditions.

2. \(f(x)=cx-c+1\) for some natural number \(c>1\), which leads to \(f(a)^{f(p)}=(ca-c+1)^{cp-c+1}\equiv ca-c+1\equiv cb-c+1=f(b)\pmod p\). But this doesn't exclusively hold when \(a\equiv b\pmod p\), as \(ca\equiv cb\pmod p\centernot\implies a\equiv b\pmod p\). Therefore, this does not fulfill the "only if" condition.

3. \(f(x)=x^n\) for some natural number \(n>1\), which leads to \(f(a)^{f(p)}=\left(a^n\right)^{p^n}\equiv a^n\equiv b^n=f(b)\pmod p\). But similar to the what we previously considered, \(a^n\equiv b^n\pmod p\centernot\implies a\equiv b\pmod p\) and this does not fulfill the "only if" condition.

4. \(f(x)=\varphi(x)+1\) where \(\varphi(x)\) is Euler's totient function, but \(a\equiv b\pmod p\centernot\implies\varphi(a)\equiv\varphi(b)\pmod p\) and therefore this does not satisfy the requirements.

5. \(f(x)=1\), which does not satisfy the "only if" condition.

Therefore, the only solution is \(f(x)=x\). \(\blacksquare\)