Задача
NT-B1-M07-P024 Простой делитель числа Ферма
#24
★★★★★ Уровень 5 из 5
Пусть \(n\ge1\), а \(p\) - нечетный простой делитель числа \(2^{2^n}+1\). Докажите, что \(p\equiv1\pmod{2^{n+1}}\).
Рассмотрите порядок числа \(2\) по модулю \(p\).
Из условия \(2^{2^n}\equiv-1\pmod p\). Возводя в квадрат, получаем \(2^{2^{n+1}}\equiv1\pmod p\). Значит, порядок \(2\) по модулю \(p\) делит \(2^{n+1}\). Но порядок не делит \(2^n\), потому что \(2^{2^n}\equiv-1\not\equiv1\pmod p\). Так как делители \(2^{n+1}\) являются степенями двойки, порядок равен \(2^{n+1}\). Порядок элемента по модулю простого \(p\) делит \(p-1\), следовательно, \(2^{n+1}\mid p-1\). Значит, \(p\equiv1\pmod{2^{n+1}}\).
Сильная задача модуля: здесь порядок становится главным объектом решения.