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 ab\)
\(\require{centernot}\)
Find all functions \(f:\mathbb N\to\mathbb N\) such that for all primes \(p\), \[p\mid f(a)^{f(p)}f(b)^p\] if and only if \(p\mid ab\).
My proposed solution:
Notice that \(p\mid ab\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:

\(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.

\(f(x)=cxc+1\) for some natural number \(c>1\), which leads to \(f(a)^{f(p)}=(cac+1)^{cpc+1}\equiv cac+1\equiv cbc+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.

\(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.

\(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.

\(f(x)=1\), which does not satisfy the "only if" condition.
Therefore, the only solution is \(f(x)=x\). \(\blacksquare\)
However, I certainly might've missed another function \(f:\mathbb N\to\mathbb N\) that fulfills the conditions. For a rigorous proof, would we need to show that all such functions have been considered? If so, how do we?
1 comment thread