Problem
NT-B2-M03-P017 General Fermat-Type Lemma
#17
★★★★★ Level 5 of 5
Let \(r\ge0\), let \(p\) be an odd prime, \(p\nmid a\), and \(p\mid a^{2^r}+1\). Prove that \(p\equiv1\pmod{2^{r+1}}\).
The order divides \(2^{r+1}\), but not \(2^r\).
From the condition \(a^{2^r}\equiv-1\pmod p\). Then \(a^{2^{r+1}}\equiv1\), so the order of \(a\) modulo \(p\) divides \(2^{r+1}\). But the order does not divide \(2^r\), otherwise \(a^{2^r}\equiv1\), not \(-1\). Among the divisors of \(2^{r+1}\), the only one not dividing \(2^r\) is \(2^{r+1}\). Hence the order is \(2^{r+1}\), and it divides \(p-1\).
This is a strong universal tool for problems with \(a^{2^r}+1\).