Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.

Question

So we obviously we want $ x^{2} + y^{2} + 1 \equiv 0 ~ (\text{mod} ~ p) $.

I haven’t learned much about quadratic congruences, so I don’t really know how to go forward. I suppose you can write it as $ x^{2} \equiv -1 - y^{2} ~ (\text{mod} ~ p) $, but again, I’m not sure where to go. I know about the Legendre symbol and quadratic residues, which I know are involved in this question, but I don’t know how to apply what I know. :(

Answer 1

Let: $$A=\{x^2|x\in \Bbb Z_p\},\ \ \ \ \ \ \ B=\{-(1+y^2)|y\in \Bbb Z_p\}$$

it is known that $$|A|=|B|=\frac{p+1}{2}$$ (maybe you can try to prove this ), if $A\cap B=\varnothing$ then $|A\cup B|=|A|+|B|=p+1>|\Bbb Z_p |$ which is impossible. as a conclusion $A\cap B$ is not empty and you're done.

Answer 2

The number of quadratic residues $\bmod p$ (prime), $|\mathcal{QR}| = \dfrac{p+1}{2}\qquad$ [1].

If we form pairs of residues $(a,b)$ such that $a+b = p-1$, we have $\frac{p-1}{2}$ distinct pairs plus $\frac{p-1}{2}$ paired with itself.

If $\frac{p-1}{2}$ is a quadratic residue, we can form the required expression using this. Otherwise, by the pigeonhole principle, one of the other residue pairs must both consist of quadratic residues - so there is $(x,y)$ with $x^2\equiv a$ and $y^2\equiv b\bmod p$. This gives the required assurance that we can form $x^2+y^2 \equiv -1 \bmod p$.

---

[1] The number of quadratic residues can be seen as a consequence of the existence of primitive roots. If $g$ is a primitive root $\bmod p$, this means that the smallest $k$ for which $g^k\equiv 1\bmod p$ is $k=p-1$. Now all the even powers of $g$, $(g^{2j})$ are quadratic residues since $g^{2j} \equiv (g^j)^2 \bmod p$, giving $(p-1)/2$ quadratic residues. Then there's one more: $0$ is a quadratic residue since $p^2\equiv 0 \bmod p$, so $(p+1)/2$ quadratic residues all together.