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