For what primes $p$ is $ (x + y)^{13} \equiv x^{13} + y^{13} \pmod{p}$, $\forall x,y \in \mathbb{Z}_p$?

Question

It is clear that $2$ and $13$ are valid values for $p$, but I can not think of any approach that would yield all possible $p$.

Answer 1

If you take $x=y=1$, then the congruence implies that $$2^{13}\equiv 2\pmod{p}$$

If you take $x=2, y=1$, then the congruence implies that $$3^{13}\equiv 2^{13}+1\equiv 3\pmod{p}$$

Continuing in this way, we find that, for all $0\le k<p$, $$k^{13}\equiv k\pmod{p}$$

In particular, the polynomial $x^{13}-x$ has $p$ roots modulo $p$. We factor $$x^{13}-x=x(x-1)(x^2+x+1)(x+1)(x^2-x+1)(x^2+1)(x^4-x^2+1)$$ This needs to have $p$ linear factors for any $p$ that works. We see immediately $p=2, 3$ work. Also, $p=13$ is the maximum possible $p$ that could work (and must, by Fermat's little theorem). For $p$ between $5,13$, we simply check to see if it has $p$ distinct roots.

Followup: $p=2,3,5,7,13$ work; $p=11$ does not. This is easily computed with alpha.

Answer 2

If it must hold for every $x,y\in\mathbb Z_p$ then in particular it must hold for $x=y=1$, and this is only true if $p\mid 2^{13}-2=8190$. So $p\in \{2,3,5,7,13\}$ and you can check these by trying all possible $x,y$.