, 2025

Solution:
We work in $\mathbb{F}_p$, treating $f$ as a map from $\mathbb{F}_p$ to itself. Clearly, $p = 2$ doesn't work. For $p > 2$ such that $5$ is a quadratic residue mod $p$, as well as $p = 5$ itself, there exists some $\alpha$ such that $(2\alpha + 1)^2\equiv 5$ (mod $p$). Taking $f(x) = \alpha x$ then works because

$$f(x + f(x)) - x = (\alpha^2 + \alpha -1)x = \frac{1}{4}\left((2\alpha +1)^2 - 5\right)x\equiv 0\pmod {p}.$$

To prove no other primes satisfy the conditions in the problem statement, note that $f$ is surjective, as for any $x$, $f(x + f(x)) = x$. As $\mathbb{F}_p$ is finite, $f$ is bijective. Plugging in $x = f(y)$ yields

$$f(f(y) + f(f(y))) = f(y)\implies f(y) + f(f(y)) = y.$$

Since $f$ is bijective, there exists $z\in \mathbb{F}_p$ such that $f(z) = 0$, then $z = f(z + f(z)) = f(z) = 0$. Therefore, $f(0) = 0$. This is the only fixed point, as any fixed point $d$ would satisfy $d = f(d) + f(f(d)) = 2d$, which is impossible if $d \neq 0$. Hence the remaining residues form nontrivial cycles $y$, $f(y)$, $f(f(y))$, etc. If the cycle containing $y$ is of length $n$, then

$$\begin{array}{rl} & f^{-1}(y) = y + f(y),\\ & f^{-2}(y) = f^{-1}(y) + y = 2y + f(y),\\ & \qquad \vdots\\ & f^{-(n - 1)}(y) = f(y) = F_ny + F_{n - 1}f(y),\\ & \qquad y = F_{n + 1}y + F_n f(y), \end{array} \quad (\text{by induction})$$

where $F_k$ is the $k$-th Fibonacci number. As $y \neq 0$ and $f(y) \neq 0$, the last two equations tell us

$$F_n^2 \equiv \left(\frac{(1 - F_{n - 1})f(y)}{y}\right) \left(\frac{(1 - F_{n + 1})y}{f(y)}\right) \equiv (F_{n + 1} - 1)(F_{n - 1} - 1) \pmod {p}.$$

Let $A = F_{n + 1} - 1$ and $B = F_{n - 1} - 1$ for brevity. The last equation becomes

$$(A - B)^2 \equiv AB \equiv \frac{1}{4} ((A + B)^2 - (A - B)^2) \pmod {p} \Longrightarrow (A + B)^2 \equiv 5(A - B)^2 \pmod {p}.$$

As $5$ is not a quadratic residue, this implies $F_{n + 1} \equiv F_{n - 1} \equiv 1 \pmod {p}$. Hence, if $d$ is the smallest positive integer such that $F_d \equiv 0 \pmod {p}$ and $F_{d + 1} \equiv 1 \pmod {p}$, then the Fibonacci sequence is periodic modulo $p$ with period $d$, so $d \mid n$. The sum of all cycle lengths (excluding the fixed point $0$) is $p - 1$, so $d \mid p - 1$. The following well-known lemma will give us a contradiction.

Lemma 1. If $5$ is not a quadratic residue modulo a prime $p$, then $p \nmid F_{p - 1}$.

Proof 1. Recall Binet's formula,

$$F_{p - 1} = \frac{1}{\sqrt{5}} \left(\left(\frac{1 + \sqrt{5}}{2}\right)^{p - 1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{p - 1}\right).$$

Multiplying both sides by $2^{p - 1}$ and expanding via the binomial theorem, we have

$$2^{p - 1}F_{p - 1} = 2\sum_{k = 0}^{\frac{p - 3}{2}}5^{k}\binom{p - 1}{2k + 1}.$$

However, $\binom{p- 1}{2k+1} \equiv(- 1)^{2k+1} \equiv- 1 \pmod{p}$ for all $k$, so

$$p \mid F_{p - 1} \quad \text{if and only if} \quad p \left| \sum_{k = 0}^{\frac{p - 3}{2}} 5^{k} = \frac{5^{\frac{p - 1}{2}} - 1}{5 - 1} \right.$$

Therefore $p \mid F_{p - 1}$ if and only if $5^{\frac{p - 1}{2}} \equiv 1 \pmod {p}$, which doesn't hold if $5$ is not a quadratic residue modulo $p$, as desired. $\square$

Proof 2. Work in $\mathbb{F}_{p^{2}} = \mathbb{F}_{p}[\sqrt{5}]$. Since $5$ is not a quadratic residue, we get that $(\sqrt{5})^{p} = - \sqrt{5}$. Using the fact that $(a + b)^{p} = a^{p} + b^{p}$ (because all other terms have coefficient divisible by $p$), we get that

$$\left(\frac{1 + \sqrt{5}}{2}\right)^{p} = \frac{1 - \sqrt{5}}{2} \implies \left(\frac{1 + \sqrt{5}}{2}\right)^{p - 1} = \left(\frac{1 - \sqrt{5}}{2}\right)^{2} = \frac{3 - \sqrt{5}}{2}.$$

Similarly, $\left(\frac{1 - \sqrt{5}}{2}\right)^{p - 1} = \frac{3 + \sqrt{5}}{2}$. Hence, by Binet's formula,

$$F_{p - 1} = \frac{1}{\sqrt{5}}\left(\left(\frac{1 + \sqrt{5}}{2}\right)^{p - 1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{p - 1}\right) = \frac{1}{\sqrt{5}}\left(\frac{3 - \sqrt{5}}{2} -\frac{3 + \sqrt{5}}{2}\right) = -1,$$

so it is not divisible by $p$.

Hence, $F_{p - 1} \neq 0$ (mod $p$) if $5$ is not a quadratic residue modulo $p$, which contradicts $d \mid p - 1$ above. This completes the solution.