Monday Math 97

Let k=2^n+1, 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=ab, with b>1 odd; we see 1≤a<n and 1<bn.

Now, recall that for integers x and y and odd positive integer m, that x^m+y^m is divisible by the integer x+y. Letting y=1, we see x+1|x^m+1.
Substituting x=2^a and m=b (as b is odd), we see
and since 1≤a<n, 1<2^a+1<2^n+1=k, we see that k has a factor 2^a+1 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 F_n=2^{2^n}+1 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 2^n+1 is a Fermat prime. Of the above list of Fermat numbers, F0, F1, F2, F3, and F4 are prime, but F5=4,294,967,297=641×6,700,417 is not prime. In fact, F0, F1, F2, F3, and F4 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).


Tags: , , , ,

One Response to “Monday Math 97”

  1. Monday Math 98 « Twisted One 151's Weblog Says:

    […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: