Difference between revisions of "Fermat prime"

(Created page with 'If <math>n</math> is a nonnegative integer the <math>n^{th}</math> '''Fermat number''' is defined to be <math>F_n = 2^{2^n}+1</math>. If <math>F_n</math> is prime, then it is kn…')
 
 
Line 1: Line 1:
If <math>n</math> is a nonnegative integer the <math>n^{th}</math> '''Fermat number''' is defined to be <math>F_n = 2^{2^n}+1</math>.
+
A '''Fermat prime''' is a [[prime number]] of the form <math>2^{2^n} + 1</math> for some [[nonnegative]] [[integer]] <math>n</math>.
  
If <math>F_n</math> is prime, then it is known as a '''Fermat prime'''. The first <math>5</math> Fermat numbers (for <math>n=0,1,2,3,4</math>) are known to be prime. Indeed:
+
A number of the form <math>2^{2^n} + 1</math> for nonnegative integer <math>n</math> is a [[Fermat number]].  The first five Fermat numbers (for <math>n=0,1,2,3,4</math>) are  
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 8: Line 8:
 
F_2 &= 2^{2^2}+1 = 17\\
 
F_2 &= 2^{2^2}+1 = 17\\
 
F_3 &= 2^{2^3}+1 = 257\\
 
F_3 &= 2^{2^3}+1 = 257\\
F_4 &= 2^{2^4}+1 = 65537.
+
F_4 &= 2^{2^4}+1 = 65537,
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
Based on these results, one might conjecture (as did [[Fermat]]) that all Fermat numbers are prime. However, this fails for <math>n=5</math>: <math>F_5 = 2^{2^5}+1 = 4294967297 = 641 \cdot 6700417</math>. In fact the primes listed above are the only Fermat numbers known to be prime.
+
and each of these is a Fermat prime.  Based on these results, one might [[conjecture]] (as did [[Fermat]]) that all Fermat numbers are prime. However, this fails for <math>n=5</math>: <math>F_5 = 2^{2^5}+1 = 4294967297 = 641 \cdot 6700417</math>. In fact, the primes listed above are the only Fermat numbers known to be prime.
  
Fermat primes are also the only primes in the form <math>2^m+1</math>. This is easy to see, if <math>m</math> has an odd factor <math>a>1</math> then <math>2^{m/a}+1|2^m+1</math>, a contradiction, hence <math>m</math> is a power of <math>2</math>.
+
== Primes one more than a power of 2 ==
 +
Fermat primes are also the only primes in the form <math>2^m+1</math>.
 +
 
 +
===Proof ===
 +
Suppose that <math>m</math> has an odd factor <math>a > 1</math>.  For all odd <math>a</math>, we have by the [[Factor Theorem | Root-Factor Theorem]] that <math>x + 1</math> divides <math>x^a + 1</math>.  Since this is true as a statement about [[polynomial]]s, it is true for every integer value of <math>x</math>.  In particular, setting <math>x = 2^{m / a}</math> gives that <math>2^{m / a} + 1 | 2^m + 1</math>, and since <math>2^m + 1 > 2^{m / a} + 1 > 1</math>, this shows that <math>2^m + 1</math> is not prime.
 +
 
 +
It follows that if <math>2^m + 1</math> is prime, <math>m</math> must have no odd [[divisor | factors]] other than <math>1</math> and so must be a power of 2.

Latest revision as of 18:07, 25 August 2009

A Fermat prime is a prime number of the form $2^{2^n} + 1$ for some nonnegative integer $n$.

A number of the form $2^{2^n} + 1$ for nonnegative integer $n$ is a Fermat number. The first five Fermat numbers (for $n=0,1,2,3,4$) are \begin{align*} F_0 &= 2^{2^0}+1 = 3\\ F_1 &= 2^{2^1}+1 = 5\\ F_2 &= 2^{2^2}+1 = 17\\ F_3 &= 2^{2^3}+1 = 257\\ F_4 &= 2^{2^4}+1 = 65537, \end{align*} and each of these is a Fermat prime. Based on these results, one might conjecture (as did Fermat) that all Fermat numbers are prime. However, this fails for $n=5$: $F_5 = 2^{2^5}+1 = 4294967297 = 641 \cdot 6700417$. In fact, the primes listed above are the only Fermat numbers known to be prime.

Primes one more than a power of 2

Fermat primes are also the only primes in the form $2^m+1$.

Proof

Suppose that $m$ has an odd factor $a > 1$. For all odd $a$, we have by the Root-Factor Theorem that $x + 1$ divides $x^a + 1$. Since this is true as a statement about polynomials, it is true for every integer value of $x$. In particular, setting $x = 2^{m / a}$ gives that $2^{m / a} + 1 | 2^m + 1$, and since $2^m + 1 > 2^{m / a} + 1 > 1$, this shows that $2^m + 1$ is not prime.

It follows that if $2^m + 1$ is prime, $m$ must have no odd factors other than $1$ and so must be a power of 2.