= Prime divisor of a Fermat number
{title2=$\operatorname{ord}_p(2)=2^{n+1}$}
For a <prime number> $p$, the exact criterion is
$$
p\mid F_n\quad\Longleftrightarrow\quad\operatorname{ord}_p(2)=2^{n+1},\qquad n\geq0,
$$
where $p$ must be different from two and $\operatorname{ord}_p(2)$ is the <multiplicative order> of two modulo $p$. If $p\mid F_n$, then $2^{2^n}\equiv-1\pmod p$: the order divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Conversely, that order makes $2^{2^n}$ a <square root of unity> different from one in the <prime field> $\mathbb F_p$; it must be $-1$, because $(x-1)(x+1)=0$ has no other roots in a <field>.
\Image[/fermat-prime-divisors-modular-orders.png]
{title=Exact modular powers distinguish Fermat divisors from the prime thirteen, whose multiplicative order is twelve}
For example, modulo seventeen the powers of two are $2,4,8,16,15,13,9,1$. Their first return to one occurs after eight steps. The half-way value is $16=-1\pmod{17}$, proving that $17\mid F_2$. Likewise, $\operatorname{ord}_{641}(2)=64$ identifies $641$ as a <prime factor> of $F_5$. These are statements about <divisibility>, not evidence that the entire <Fermat number> is prime.
The <multiplicative order> always divides $p-1$, by <Fermat's little theorem>, so $p\equiv1\pmod{2^{n+1}}$. In particular, for $n\geq1$ every <prime divisor of a Fermat number> is one modulo four. That weaker <modular congruence> is insufficient: thirteen is one modulo four, but $\operatorname{ord}_{13}(2)=12$, which is not a <power of two>. It divides no <Fermat number> at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.
Back to article page
