Задача
NT-B2-M09-P014 Решения квадрата по модулю 840
#14
★★★★☆ Уровень 4 из 5
Сколько решений имеет сравнение \(x^2\equiv 1\pmod {840}\)?
Разложите \(840=8\cdot 3\cdot 5\cdot 7\).
Модули \(8,3,5,7\) попарно взаимно просты. По модулю \(8\) все нечётные остатки \(1,3,5,7\) дают квадрат \(1\), значит \(4\) решения. По каждому из модулей \(3,5,7\) есть по \(2\) решения: \(\pm 1\). Всего по CRT получаем \(4\cdot 2\cdot 2\cdot 2=32\) решения.
Важный пример: степень двойки ведёт себя иначе, чем нечётный простой модуль.