Problem
NT-B2-M02-P012 A Congruence Modulo a Composite Number
#12
★★★★☆ Level 4 of 5
Solve the congruence \(x^2\equiv4\pmod{15}\).
Solve separately modulo \(3\) and modulo \(5\), then combine the conditions.
The condition is equivalent to \(x^2\equiv1\pmod3\) and \(x^2\equiv4\pmod5\). The first gives \(x\not\equiv0\pmod3\), and the second gives \(x\equiv\pm2\pmod5\). Combining the classes gives \(x\equiv2,7,8,13\pmod{15}\).
Here CRT appears as a tool for quadratic congruences.