$x^4 + y^4 \mod p$

Solution 1:

For a given prime $p$, let $Z_p$ denote the ring of integers, mod $p$, and let $f\colon Z_p^2 \to Z_p$ be defined by $f(x,y) = x^4+y^4$.

Partial result: If $p \equiv -1\;\,(\text{mod}\;4)$, then $f$ is surjective.

Proof:

Assume $p$ is a prime, with $p \equiv -1\;\,(\text{mod}\;4)$.

Then $-1$ is not a quadratic residue, mod $p$.

Claim every square in $Z_p$ is also a $4$-th power.

Let $a,b \in Z_p^{*}$, and suppose $a^4=b^4$ in $Z_p$. \begin{align*} \text{Then in $Z_p$,}\;\;&a^4=b^4\\[4pt] \implies\;&a^2=\pm b^2\\[4pt] \implies\;&a^2=b^2&&\text{[since $-1$ is not a quadratic residue, mod $p$]}\\[4pt] \implies\;&a= \pm b\\[4pt] \end{align*} It follows that the map $Z_p^{*} \to Z_p^{*}$ given by $x \mapsto x^4$ is exactly two-to-one, hence the set of $4$-th powers in $Z_p^{*}$ has cardinality $\frac {p-1}{2}$. Of course every $4$-th power is also a square, hence, since the cardinalities are the same, the set of $4$-th powers in $Z_p^{*}$ is the same as the set of squares in $Z_p^{*}$, which (since $0$ is also a $4$-th power), proves the claim.

For any $k \in Z_p$ which is not a square in $Z_p$, $$Z_p = \{x^2 \mid x \in Z_p\} \cup \{kx^2 \mid x \in Z_p^{*}\}$$ Fix $k \in \{0,1,2,...,p-1\}$ as the least positive integer such that $k$ is not a square in $Z_p$. Then $k > 1$, and $k-1$ is a square in $Z_p$.

Fix $r$ is $Z_p$. We want to show $r$ is in the image of $f$.

If $r$ is a square in $Z_p$, then $r$ is a $4$-th power in $Z_p$, hence $f(x,0)=r$, for some $x$, so $r$ is in the image of $f$.

Next, suppose $r$ is not a square in $Z_p$.

Then $r=kx^2$, for some $x \in Z_p$, and $(k-1)x^2$ is a square in $Z_p$.

Let $y$ be such that $y^2 = (k-1)x^2$ in $Z_p$. \begin{align*} \text{Then in $Z_p$,}\;\;&y^2=(k-1)x^2\\[4pt] \implies\;&x^2+y^2=kx^2\\[4pt] \implies\;&x^2+y^2=r\\[4pt] \implies\;&\text{$r$ is the sum of two squares}\\[4pt] \implies\;&\text{$r$ is the sum of two $4$-th powers}\\[4pt] \end{align*} hence $r$ is in the image of $f$, as required.