Fermat Number Proof

Date: 01/30/2001 at 00:26:36
From: Robyn
Subject: Fermat numbers

Dr. Math,

Two questions: 

1) Prove that if n > 0, then the Fermat number 2^2^n + 1 is of the 
form 9k-1 or 9k-4.  

2) Prove that n and 2^2^n + 1 are relatively prime for every n > 0.  

Answers would be appreciated!

Robyn

Date: 01/30/2001 at 12:41:52
From: Doctor Rob
Subject: Re: Fermat numbers

Thanks for writing to Ask Dr. Math, Robyn.

The first proof starts with Euler's Theorem:

   If (a,n) = 1, then a^phi(n) = 1 (mod n), where phi is the Euler
   phi function.

Apply this with a = 2 and n = 9.  Then phi(9) = 6, so

   2^6 = 1 (mod 9).

Thus for any nonnegative integer s,

   2^(6*s) = 2^0 = 1 (mod 9).

That means that the exponent of 2 can be reduced modulo 6.

You cannot apply Euler's Theorem with a = 2 and n = 6, because
(a,n) = 2 > 1.  Now it is obvious that 2^n = 0 (mod 2) and Euler's
theorem says that 2^2 = 1 (mod 3).  This implies that for any
nonnegative integer r, 2^(2*r) = 1 (mod 3) and 2^(2*r+1) = 2 (mod 3).
Using the Chinese Remainder Theorem, that means that for any
nonnegative integer r,

     2^(2*r) = 4 (mod 6),
   2^(2*r+1) = 2 (mod 6).

Now you can finish be evaluating 2^(2^n) + 1 modulo 9 when n = 2*r
and when n = 2*r + 1.


To prove that 2^(2^n) + 1 and n are relatively prime, it suffices to
show that every prime divisor p of 2^(2^n) + 1 has the form
p = k*2^(n+1) + 1 for some k > 0.  (This was proven by Leonhard
Euler in 1770.)

Obviously any prime divisor p of 2^(2^n) + 1 must be odd.  Now let e
be the order of 2 modulo p, that is, the least exponent such that
2^e = 1 (mod p).  Obviously e > 1.  Since

   2^(2^(n+1)) = 1 (mod p),

it must be that e | 2^(n+1).  Write

   r*e = 2^(n+1).

Then obviously r and e are both powers of 2.  Since e > 1, e/2 is an
integer, and then

   2^(e/2) = -1 (mod p).

Thus

   -1 = 2^(2^n) = 2^(e*r/2) = [2^(e/2)]^r = (-1)^r = -1 (mod p),

so that r must be odd.  Since r is a power of 2, obviously r = 1, so
that

   e = 2^(n+1).

That proves that 2^(n+1) | p - 1.  Let

   k = (p-1)/2^(n+1) >= 1,

and then solve for p to get

   p = k*2^(n+1) + 1.

Q.E.D.

Now use that to show that if p is a prime divisor of 2^(2^n) + 1,
that p cannot divide n, and you'll be done.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/