Задача
NT-B1-M07-P022 Делитель числа \(a^2+1\)
#22
★★★★☆ Уровень 4 из 5
Пусть \(p\) - нечетное простое число, \(p\mid a^2+1\) и \(p\nmid a\). Докажите, что \(p\equiv1\pmod4\).
Из \(a^2\equiv-1\pmod p\) найдите порядок \(a\) по модулю \(p\).
Имеем \(a^2\equiv-1\pmod p\). Тогда \(a^4\equiv1\pmod p\), но \(a^2\not\equiv1\pmod p\), так как это означало бы \(-1\equiv1\pmod p\), то есть \(p=2\). Значит, порядок \(a\) по модулю \(p\) равен \(4\). Порядок делит \(p-1\), поэтому \(4\mid p-1\), то есть \(p\equiv1\pmod4\).
Первое серьезное применение порядка как ограничения на простой делитель.