Let , *n* a positive integer. If *k* is prime (an odd prime, as *k*>2), show that n must be a power of two.

Let *n* be a positive integer but not a power of 2. Then it must have at least one prime factor that is not two, and thus must have at least one odd factor greater than 1. So let *n*=*a**b*, with *b*>1 odd; we see 1≤*a*<*n* and 1<*b*≤*n*.

Now, recall that for integers *x* and *y* and odd positive integer *m*, that is divisible by the integer *x*+*y*. Letting *y*=1, we see .

Substituting and *m*=*b* (as *b* is odd), we see

,

and since 1≤*a*<*n*, , we see that *k* has a factor which is neither unity nor *k* itself. Thus, if *n* is not a power of 2, then *k* cannot be prime. So if *k* is prime, *n* is a power of 2.

The numbers are known as Fermat numbers. The first few Fermat numbers are:

Those Fermat numbers which are prime are called Fermat primes. So our proof was that every prime of the form is a Fermat prime. Of the above list of Fermat numbers, *F*_{0}, *F*_{1}, *F*_{2}, *F*_{3}, and *F*_{4} are prime, but *F*_{5}=4,294,967,297=641×6,700,417 is not prime. In fact, *F*_{0}, *F*_{1}, *F*_{2}, *F*_{3}, and *F*_{4} are the only known Fermat primes. However, as the Fermat numbers grow so rapidly, little is yet known about those for large *n*, and there are a number of open problems, including whether there are any other Fermat primes besides those listed above, and if there are infinitely many or finitely many Fermat primes (see here).

### Like this:

Like Loading...

*Related*

Tags: Fermat Number, Fermat Prime, Math, Monday Math, Prime Numbers

This entry was posted on November 16, 2009 at 1:37 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

February 25, 2010 at 11:59 pm |

[…] be able to give a power of 2 only if is a power of 2, which means that p is of the form . I proved last week that the only primes of this form are the Fermat primes, primes of the form . Thus, the above is […]