Problem
NT-B1-M07-P024 A Prime Divisor of a Fermat Number
#24
★★★★★ Level 5 of 5
Let \(n\ge1\), and let \(p\) be an odd prime divisor of \(2^{2^n}+1\). Prove that \(p\equiv1\pmod{2^{n+1}}\).
Consider the order of \(2\) modulo \(p\).
From the condition, \(2^{2^n}\equiv-1\pmod p\). Squaring gives \(2^{2^{n+1}}\equiv1\pmod p\). Thus the order of \(2\) modulo \(p\) divides \(2^{n+1}\). But it does not divide \(2^n\), because \(2^{2^n}\equiv-1\not\equiv1\pmod p\). Since all divisors of \(2^{n+1}\) are powers of two, the order is \(2^{n+1}\). The order of an element modulo prime \(p\) divides \(p-1\), hence \(2^{n+1}\mid p-1\). Therefore \(p\equiv1\pmod{2^{n+1}}\).
Challenge problem: here the order becomes the main object of the solution.