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$

  • $\begingroup$ @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) $\endgroup$ – Spasoje Durovic Apr 18 at 13:52
  • $\begingroup$ 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 $\endgroup$ – WaveX Apr 18 at 13:55
  • 2
    $\begingroup$ Hint. You are almost there. $(x/y)^2$ will be $-1$ modulo $p$, where $1/y$ is the inverse of $y$ mod $p$. $\endgroup$ – Ethan Bolker Apr 18 at 13:56
  • $\begingroup$ @EthanBolker I completed the proof with your suggestion, thanks :) $\endgroup$ – Spasoje Durovic Apr 18 at 13:59

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.