Problem
NT-B1-M03-P015 Sum of Two Squares Divisible by 3
#15
★★★☆☆ Level 3 of 5
Prove: if \(3\mid x^2+y^2\), then \(3\mid x\) and \(3\mid y\).
Squares modulo \(3\) are \(0\) or \(1\).
If a number is not divisible by \(3\), its square has residue \(1\) modulo \(3\). If at least one of \(x,y\) is not divisible by \(3\), the sum of squares has residue \(1\) or \(2\), not \(0\), except when both squares are \(0\). Therefore both \(x\) and \(y\) are divisible by \(3\).
Preparation for the descent problem at the end of the module.