Problem
NT-B2-M03-P015 A Divisor of \(2^{16}+1\)
#15
★★★★☆ Level 4 of 5
Let a prime \(q\mid2^{16}+1\). Prove that \(q\equiv1\pmod{32}\).
Show that the order of \(2\) modulo \(q\) is \(32\).
The number \(2^{16}+1\) is odd, so \(q\ne2\). From \(2^{16}\equiv-1\pmod q\), we get \(2^{32}\equiv1\). Also \(2^{16}\not\equiv1\), and the order divides \(32\). The only divisor of \(32\) that does not divide \(16\) is \(32\). Thus the order of \(2\) modulo \(q\) is \(32\). Therefore \(32\mid q-1\), so \(q\equiv1\pmod{32}\).
This is a concrete version of the general Fermat-type lemma.