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: | ||
| − | + | A '''Fermat prime''' is a [[prime number]] of the form <math>2^{2^n} + 1</math> for some [[nonnegative]] [[integer]] <math>n</math>. | |
| − | + | 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>. | + | == 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 17:07, 25 August 2009
A Fermat prime is a prime number of the form 
for some nonnegative integer 
.
A number of the form for nonnegative integer is a Fermat number. The first five Fermat numbers (for 
) are
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 
: 
. 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 
.
Proof
Suppose that 
has an odd factor 
. For all odd 
, we have by the Root-Factor Theorem that 
divides 
. Since this is true as a statement about polynomials, it is true for every integer value of 
. In particular, setting 
gives that 
, and since 
, this shows that 
is not prime.
It follows that if is prime, must have no odd factors other than 
and so must be a power of 2.
