Problem
NT-B2-M09-P014 Square Roots of One Modulo 840
#14
★★★★☆ Level 4 of 5
How many solutions does \(x^2\equiv 1\pmod {840}\) have?
Factor \(840=8\cdot 3\cdot 5\cdot 7\).
The moduli \(8,3,5,7\) are pairwise coprime. Modulo \(8\), all odd residues \(1,3,5,7\) square to \(1\), so there are \(4\) solutions. For each of \(3,5,7\), there are \(2\) solutions: \(\pm 1\). By CRT, the total number is \(4\cdot 2\cdot 2\cdot 2=32\).
Important example: a power of two behaves differently from odd prime moduli.