Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search