Editing Fermat number (section)

===Equivalent conditions===
{{Main|Pépin's test}}

Let <math>F_n=2^{2^n}+1</math> be the ''n''th Fermat number. Pépin's test states that for {{nowrap|''n'' > 0}},

:<math>F_n</math> is prime if and only if <math>3^{(F_n-1)/2}\equiv-1\pmod{F_n}.</math>

The expression <math>3^{(F_n-1)/2}</math> can be evaluated modulo <math>F_n</math> by [[exponentiation by squaring|repeated squaring]]. This makes the test a fast [[polynomial-time]] algorithm. But Fermat numbers grow so rapidly that only a handful of them can be tested in a reasonable amount of time and space.

There are some tests for numbers of the form {{nowrap|''k''{{space|hair}}2<sup>''m''</sup> + 1}}, such as factors of Fermat numbers, for primality.

:'''[[Proth's theorem]]''' (1878). Let {{nowrap|1=''N'' = ''k''{{space|hair}}2<sup>''m''</sup> + 1}} with odd {{nowrap|''k'' < 2<sup>''m''</sup>}}. If there is an integer ''a'' such that
:: <math>a^{(N-1)/2} \equiv -1\pmod{N}</math>
:then <math>N</math> is prime. Conversely, if the above congruence does not hold, and in addition
:: <math>\left(\frac{a}{N}\right)=-1</math> (See [[Jacobi symbol]])
:then <math>N</math> is composite.

If {{nowrap|1=''N'' = ''F''<sub>''n''</sub> > 3}}, then the above Jacobi symbol is always equal to −1 for {{nowrap|1=''a'' = 3}}, and this special case of Proth's theorem is known as [[Pépin's test]]. Although Pépin's test and Proth's theorem have been implemented on computers to prove the compositeness of some Fermat numbers, neither test gives a specific nontrivial factor. In fact, no specific prime factors are known for {{nowrap|1=''n'' = 20}} and&nbsp;24.