# Divisibility of $x^2+y^2$ by prime $p$

I've read the following fact on my number theory textbook, there's no proof on the book of such result, I tried working it out on my own but I'm kinda lost, the lemma is the following:

Given two integers $$a,b$$ and a prime of the form $$p=4q+3$$, $$p|a^2+b^2$$ $$\iff p|a$$ and $$p|b$$

I would post my work but I doubt it would be of any help since I don't feel I got anywhere, I tried analyzing $$x^2+y^2\equiv0 \pmod p$$ since $$x^2\equiv-y^2$$ looked somewhat promising to me, the only thing I noticed is that $$x^2 \neq-1\pmod p$$ since $$p\equiv3\pmod4$$

• @Clayton Not really, the book states this fact in a solution of a problem, this is what it says: "We shall use the following well-known fact: if $p$ is prime of the form $4q + 3$ and if it divides $x^2 + y^2$ then $p$ divides $x$ and $y$. (the book is Titu Andreescu's olympiad number theory) – Spasoje Durovic Apr 18 at 13:52
• Going from right to left is the easier of the two parts: $a = mp$ and $b=np$ so we have that $a^2+b^2 = p(pm^2+pn^2)$ so really the part that needs to be figured out is left to right – WaveX Apr 18 at 13:55
• Hint. You are almost there. $(x/y)^2$ will be $-1$ modulo $p$, where $1/y$ is the inverse of $y$ mod $p$. – Ethan Bolker Apr 18 at 13:56
• @EthanBolker I completed the proof with your suggestion, thanks :) – Spasoje Durovic Apr 18 at 13:59

## 1 Answer

As suggested by Ethan Bolker in the comments, continuing my line of reasoning we have: $$x^2\equiv-y^2\pmod p$$ If $$p$$ divides $$y$$ we're done, otherwise suppose $$p$$ doesn't divide $$y$$, then $$p$$ can't divide $$y^{-1}$$ (its modular inverse) either since if it did: $$y\cdot y^{-1}\equiv y\cdot0\equiv0\neq1\pmod p$$ Thus we can multiply both sides of the first conguence by $$(y^{-1})^2$$ without changing the mod since $$(y^{-1},p)=1$$, thus:$$x^2\cdot (y^{-1})^2\equiv(x\cdot y^{-1})^2\equiv-1\pmod p$$ Which is a contradiction because $$k^2\equiv -1 \pmod p \iff p\equiv 1 \pmod4$$