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

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. :(

• Showing that infinitely many primes have the form $x^2+y^2+1$ is much more difficult, see here. – Watson Dec 1 '18 at 21:18
• – Watson Dec 2 '18 at 11:26

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.

• In the contradiction step, do you mean union instead of intersection? – shardulc May 1 '15 at 18:00
• Yes you're right, in order to prove the claim $|A|=|B|=\frac{p+1}{2}$, can be done in two steps , first notice that $|A|=|B|$ they have the same cardinals which is the number of squares in $\Bbb Z_p$ ( bujection $A:\to B\ \ x\to -(1+x)$) and in order to find the number of squares you can look in the internet for "the number of squares in $\Bbb Z_p$ " don't forget that $0$ is olso a square and good luck – Elaqqad May 1 '15 at 18:12
• +1. Nice elegant argument. In fact, this shows that for any prime $p$ and any $k \in \mathbb{Z}_p$, there exists $x,y$ such that $x^2+y^2 \equiv k \pmod{p}$. – Leg May 1 '15 at 18:17
• Yes this is correct – Elaqqad May 1 '15 at 18:20
• I know that there are (p-1)/2 squares in (z/pz)* and (p+1)/2 squares in (z/pz), but how does knowing that let me show there are always solutions for this congruence? :( I'm afraid I have never done union and intersection kinds of proofs before, so I'm not sure I get your answer Elaqqad. Also, @user17762, If I am right in assuming that Zp are the positive integers, how does that work for my needing k=-1? Thank you so much for your help! – user236028 May 4 '15 at 16:49

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

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. This gives the required assurance that we can form $x^2+y^2 \equiv -1 \bmod p$.