Задача
NT-B2-M03-P017 Общая ферматова лемма
#17
★★★★★ Уровень 5 из 5
Пусть \(r\ge0\), \(p\) - нечётный простой, \(p\nmid a\), и \(p\mid a^{2^r}+1\). Докажите, что \(p\equiv1\pmod{2^{r+1}}\).
Порядок делит \(2^{r+1}\), но не делит \(2^r\).
Из условия \(a^{2^r}\equiv-1\pmod p\). Тогда \(a^{2^{r+1}}\equiv1\), значит порядок \(a\) по модулю \(p\) делит \(2^{r+1}\). Но порядок не делит \(2^r\), потому что тогда \(a^{2^r}\equiv1\), а не \(-1\). Среди делителей \(2^{r+1}\) единственный, который не делит \(2^r\), равен \(2^{r+1}\). Значит, порядок равен \(2^{r+1}\), и он делит \(p-1\).
Это сильный универсальный инструмент для задач с \(a^{2^r}+1\).