Quadratic Residues Modulo Prime

[Nirjhor]

For any fixed prime $p$, prove that for all $0\le r\le p-1$ there exist two quadratic residues modulo $p$ that add up to $r$. In other words, prove that for all primes $p$ there exist two integers $m$ and $n$ such that \[m^2+n^2\equiv r\pmod p\] where $0\le r\le p-1$ is a fixed integer.

[Phlembac Adib Hasan]

"...that add up to $n$". I think it's $r$. The following solution is based on this assumption. If that's not the case, inform us.
I'll take mod $p$ everywhere. Let $z$ be the primitive root of $p$. For $r=0$, we have $r\equiv p^2+p^2$. And if $r\equiv z^{2i}$ we can simply take $(z^i)^2+p^2$. So it is sufficient to prove the statement for $r\equiv z^{2i+1}$.
I claim there are $a,b$ such that $z^{2a}+1\equiv z^{2b+1}\quad (1)$. If not, then $z^2+1\equiv z^{2\Psi_1}$. Similarly $z^2+2\equiv z^{2\Psi_1}+1\equiv z^{2\Psi_2}$ and so on. But there are only $(p-1)/2$ quad. residues. So we may find only $(p-1)/2$ such consecutive integers. But there are $p-1$ different residues. So ultimately we'll end up at a solution of $(1)$. Let $k=(i-b)+\frac{3(p-1)}2$. So $z^{2(a+k)}+z^{2k}\equiv z^{2i+1+3(p-1)}\equiv r$. So done.

[Nirjhor]

Yeah sorry that would be $r$. Edited now.

But how do we know that $z^2+1\equiv z^{2\Phi_1}$ for integer $\Phi_1$?

[Phlembac Adib Hasan]

To prove that (1) has at least one solution, I simply assumed it doesn't have any solution. And from this assumption, any quad.residue+1$\equiv $ another quad. residue, provided the later is not a multiple of $p$. I started from $z^2$ out of no reason. But as it seems, it leaves a little gap in the logic. Someone might argue what if $z^2+1$ is a multiple of $p$? ie in case of $p=5$? Well it doesn't nullify my argument. I can start from $z^{p-1}\equiv 1$. So $i+1\equiv z^{p-1}+i\equiv z^{2\Psi_{i-1}}+1\equiv z^{2\Psi_i}$
I was not too concerned about rigorousness, If my reasoning is correct, someone else might correct the little flaws.

[Fm Jakaria]

Another solution:

Consider the two sets $X,Y$ of residue classes (mod p) as defined next:
$X$ contains squares of classes through $0$ to $\frac{p-1}{2}$. $Y$ contains classes of form $(r-t)$; for t$\in X$.
It is obvious that there are exactly $\frac{p+1}{2}$ elements in both $X$ and $Y$. As $A \cup B$ can contain at most p elements, it follows that $X,Y$ has nonempty intersection. This completes the proof: $\exists a,b \in \mathbb{N}$
so that $a^2+b^2 \equiv r\pmod p$

[*Mahi*]

Note: If we find one quadratic non-residue $\equiv a^2+b^2 \pmod p$, we are done as we can multiply both sides with $z^2$ where $z$ is a primitive root and cycle through the other quadratic non-residues.
Now, assume the contrary, it yields $\text{every quadratic residue}+1 = \text{another quadratic residue}$, which, by induction implies every $r \in 0\le r\le p-1 $ is a quadratic residue, which is indeed false.

[Nirjhor]

Note: If we find one quadratic non-residue $\equiv a^2+b^2 \pmod p$, we are done as we can multiply both sides with $z^2$ where $z$ is a primitive root and cycle through the other quadratic non-residues.
Now, assume the contrary, it yields $\text{every quadratic residue}+1 = \text{another quadratic residue}$, which, by induction implies every $r \in 0\le r\le p-1 $ is a quadratic residue, which is indeed false.

I was having a little difficulty to understand this part from Adib bhai's solution. Otherwise that is the same solution I found.