Задача
NT-B2-M03-P015 Делитель \(2^{16}+1\)
#15
★★★★☆ Уровень 4 из 5
Пусть простой \(q\mid2^{16}+1\). Докажите, что \(q\equiv1\pmod{32}\).
Покажите, что порядок \(2\) по модулю \(q\) равен \(32\).
Число \(2^{16}+1\) нечётно, значит \(q\ne2\). Из \(2^{16}\equiv-1\pmod q\) получаем \(2^{32}\equiv1\). При этом \(2^{16}\not\equiv1\), а порядок делит \(32\). Единственный делитель \(32\), который не делит \(16\), равен \(32\). Значит, порядок \(2\) по модулю \(q\) равен \(32\). Поэтому \(32\mid q-1\), то есть \(q\equiv1\pmod{32}\).
Это конкретный вариант общей ферматовой леммы.