Задача
NT-B2-M02-P012 Сравнение по составному модулю
#12
★★★★☆ Уровень 4 из 5
Решите сравнение \(x^2\equiv4\pmod{15}\).
Решите отдельно по модулям \(3\) и \(5\), затем совместите условия.
Условие равносильно \(x^2\equiv1\pmod3\) и \(x^2\equiv4\pmod5\). Первое даёт \(x\not\equiv0\pmod3\), второе даёт \(x\equiv\pm2\pmod5\). Совмещая классы, получаем \(x\equiv2,7,8,13\pmod{15}\).
Здесь появляется CRT как инструмент для квадратичных сравнений.