The answer is $p$. Ignore $p=2$. Notice $x^2$ can take on $\frac{p+1}{2}$ residues. Fix a residue $k$. Assume there are no two $x$ and $y$ in this set for which $x+y\equiv k$ then pair up the residues mod $p$ into $\frac{k}{2}$ and $\frac{p-1}{2}$ pairs summing to $k$ so $x^2$ can take on at most $\frac{p-1}{2}$ values, a contradiction.

Perhaps a more transparent way. For any reside $x$, consider the sets (modulo $p$) \[ A = \{t^2:0\le t\le (p-1)/2\}\quad\text{and}\quad B_x = \{x-u^2:0\le u\le (p-1)/2\}. \]Notice that $|A|=|B_x|=(p+1)/2$. If $A$ and $B_x$ are disjoint, then $|A\cup B_x| = |A|+|B_x| = p+1$, but $A\cup B_x$, being a subset of $\{1,\dots,p\}$ (modulo $p$), has cardinality at most $p$, a contradiction. So $A\cap B_x = \varnothing$, hence the proof.

$a^2$ takes $\frac{p+1}{2}$ values mod $p$, so by Cauchy-Davenopt theorem $a^2+b^2$ takes at least $\frac{p+1}{2}+\frac{p+1}{2}-1=p$ values, so all are taken When $p=2$, $0+1=1$ and $0+0=0$

atdaotlohbh wrote: $a^2$ takes $\frac{p+1}{2}$ values mod $p$, so by Cauchy-Davenopt theorem $a^2+b^2$ takes at least $\frac{p+1}{2}+\frac{p+1}{2}-1=p$ values, so all are taken When $p=2$, $0+1=1$ and $0+0=0$ Cauchy-Davenopt Theorem only works on the reals not under modulo arithmetic.

Nope. Cauchy-Davenport theorem states the result in modulo prime arithmetic, I do not know the name of the result on the reals. Here is a link to read about this theorem https://sites.math.rutgers.edu/~sk1233/courses/additive-F16/lec1.pdf

atdaotlohbh wrote: Nope. Cauchy-Davenport theorem states the result in modulo prime arithmetic, I do not know the name of the result on the reals. Here is a link to read about this theorem https://sites.math.rutgers.edu/~sk1233/courses/additive-F16/lec1.pdf Sorry, I was familiar with only the special case of this theorem over the reals. Your approach is then probably best for solving this problem.

Note that all QRs occur for sure. Further, one of the numbers $x^2+1$ is a QNR, so all QNRs occur as well. Thus all residues occur. (This is for $p$ odd as $p=2$ is trivial)