Задача
NT-B2-M02-P014 Минус единица по модулю \(65\)
#14
★★★★☆ Уровень 4 из 5
Решите сравнение \(x^2\equiv-1\pmod{65}\).
Используйте \(65=5\cdot13\).
Нужно решить \(x^2\equiv-1\pmod5\) и \(x^2\equiv-1\pmod{13}\). По модулю \(5\): \(x\equiv\pm2\). По модулю \(13\): \(x\equiv\pm5\). Совмещая четыре пары условий по CRT, получаем \(x\equiv8,18,47,57\pmod{65}\).
Эта задача связывает квадратичные остатки с CRT, не вводя символ Лежандра.