
Opgave 4. Vind alle functies $f: \mathbb{Z} \rightarrow \mathbb{Z}$ die voldoen aan

- $f(p)>0$ voor alle priemgetallen $p$,
- $p \mid(f(x)+f(p))^{f(p)}-x$ voor alle $x \in \mathbb{Z}$ en alle priemgetallen $p$.


Oplossing. Vul $x=p$ in: $p \mid(2 f(p))^{f(p)}-p$ en $p$ is priem, dus $p \mid 2 f(p)$. We zien dat $p=2$ of $p \mid f(p)$. Vul nu $x=0$ in: $p \mid(f(0)+f(p))^{f(p)}-0$ en $p$ is priem, dus $p \mid f(0)+f(p)$. Aangezien $p \mid f(p)$ voor $p \neq 2$, zien we nu ook $p \mid f(0)$ voor $p \neq 2$. Dus $f(0)$ is deelbaar door oneindig veel priemgetallen en moet daarom wel 0 zijn. Nu volgt uit $2 \mid f(0)+f(2)$ ook dat $2 \mid f(2)$, dus $p \mid f(p)$ voor alle priemgetallen $p$.

De gegeven deelrelatie laat zich nu vertalen tot $f(x)^{f(p)} \equiv x \bmod p$ voor alle gehele getallen $x$ en priemgetallen $p$. We zien dat $p \mid f(x)$ dan en slechts dan als $p \mid x$. Als we dit nu toepassen voor $x=q$ met $q$ een priemgetal ongelijk aan $p$, dan zien we dat $f(q)$ door geen enkele $p \neq q$ deelbaar is en dus wel een macht van $q$ moet zijn. De kleine stelling van Fermat zegt voor alle priemgetallen $p$ en gehele getallen $n$ dat $n^{p} \equiv n \bmod p$, dus ook $n^{p^{t}} \equiv n \bmod p$ voor alle positieve gehele $t$. Nu is $f(p)$ voor alle priemgetallen $p$ van de vorm $p^{t}$ met $t$ positief geheel, dus uit de gegeven deelrelatie kunnen we nu concluderen dat $f(x) \equiv x \bmod p$ voor alle gehele getallen $x$ en priemgetallen $p$. Dus $p \mid f(x)-x$ voor alle $x$ en $p$. Dus voor een vaste $x \in \mathbb{Z}$ geldt dat $f(x)-x$ deelbaar is door oneindig veel priemgetallen $p$, waaruit volgt dat $f(x)-x=0$. Dus $f(x)=x$ voor alle $x$. We controleren deze functie. Er geldt inderdaad $f(p)>0$ voor priemgetallen $p$. En verder is

$$
(f(x)+f(p))^{f(p)}-x=(x+p)^{p}-x \equiv x^{p}-x \equiv 0 \quad \bmod p
$$

voor alle $x \in \mathbb{Z}$ en alle priemgetallen $p$. Dus de functie $f(x)=x$ voldoet.

