Problem
NT-B2-M02-P011 A Prime \(3\pmod4\)
#11
★★★☆☆ Level 3 of 5
Let \(p\equiv3\pmod4\) be prime and \(p\mid x^2+y^2\). Prove that \(p\mid x\) and \(p\mid y\).
If \(p\nmid y\), divide the congruence by \(y^2\).
Assume \(p\nmid y\). Then \(y^{-1}\pmod p\) exists, and \(x^2+y^2\equiv0\) gives \((xy^{-1})^2\equiv-1\pmod p\). But for a prime \(p\equiv3\pmod4\), \(-1\) is not a square. Contradiction. Hence \(p\mid y\), and then \(p\mid x^2+y^2\) gives \(p\mid x^2\), so \(p\mid x\).
This is the main lemma for the theorem on sums of two squares.