Problem
NT-B1-M06-P014 A Sum of Squares Modulo \(7\)
#14
★★★☆☆ Level 3 of 5
Prove that if \(7\mid x^2+y^2\), then \(7\mid x\) and \(7\mid y\).
Squares modulo \(7\) are \(0,1,2,4\).
The quadratic residues modulo \(7\) are \(0,1,2,4\). No two nonzero elements of \(\{1,2,4\}\) sum to \(0\) modulo \(7\). Hence \(x^2+y^2\equiv0\pmod7\) is possible only when \(x^2\equiv y^2\equiv0\pmod7\). Therefore \(7\mid x\), \(7\mid y\).
Good practice with a quadratic-residue table.