If $p=4k+3$ is prime then exist $x$, $y\in\mathbb{Z}$ such that $p| (x^2+y^2+1)$

Question

i have an exam test question in arithmetic: If $p=4k+3$ is prime then exist $x$, $y\in\mathbb{Z}$ such that $p| (x^2+y^2+1)$. Is that anyway to prove this?

Answer 1

Hint:

This is the same as showing that there exists $x,y\in\mathbb Z$ such that $$x^2+y^2\equiv_p -1\iff x^2\equiv_p -1-y^2$$

Try to count the number of elements in $\mathbb Z_p$ that can be written as $x^2$, and the number of elements that can be written as $-1-y^2$. Let

• $A=\{x^2\mid x\in\mathbb Z_p\}$
• $B=\{-1-y^2\mid y\in\mathbb Z_p\}$

How is $|A|$ and $|B|$ related? Also, which one on the options below is true?

• $|A|+|B|>p$
• $|A|+|B|=p$
• $|A|+|B|<p$

Lemma 1: Let $R$ be the set of quadratic residues (note! not including $0$), and $N$ the set of quadratic non-residues. Then, $$|R|=|N|=\frac{p-1}{2}$$ Proof: Define a group homomorphism $$\phi:\mathbb Z_p^\times\rightarrow\mathbb Z_p^\times$$ by $\phi(x)=x^2$. We have that $\text{im}(\phi)=R$, and $\ker(\phi)=\{-1,1\}$. By the 1st isomorphism theorem $$R=\text{im}(\phi)\cong\mathbb Z_p^\times/\ker(\phi)$$ and so $|R|=\frac{p-1}{2}$. Therefore $$|\mathbb Z_p^\times|=p-1=|R|+|N|\\\Rightarrow |R|=|N|=\frac{p-1}{2}$$