Problem
NT-B1-M06-P020 A Primitive Sum of Squares
#20
★★★☆☆ Level 3 of 5
Let \(\gcd(x,y)=1\). Prove that \(x^2+y^2\) is not divisible by \(3\).
If the sum is divisible by \(3\), use the problem about square residues modulo \(3\).
Suppose \(3\mid x^2+y^2\). Then modulo \(3\), both squares must be \(0\), so \(3\mid x\) and \(3\mid y\). This contradicts \(\gcd(x,y)=1\). Therefore \(x^2+y^2\) is not divisible by \(3\).
Important idea: first pass to a primitive solution.