The Fermat numbers are numbers of the form
Fermat thought that all the were prime. The first
five are:
However, it turns out that . Note
that
Therefore,
Here x is an integer.
On the other hand, , so
This proves that .
A Fermat prime is a Fermat number which is prime. It is an open question as to whether there are infinitely many Fermat primes.
Surprisingly, Fermat primes arise in deciding whether a regular n-gon (a convex polygon with n equal sides) can be constructed with a compass and a straightedge. Gauss showed that a regular n-gon is contructible with a compass and a straightedge if and only if n is a power of 2 times a product of distinct Fermat primes.
Here are some properties of the Fermat numbers.
Proposition. If p is prime and , then
for some
k.
I won't prove this result, since the proof requires results about quadratic residues which I won't discuss for a while. Here's how it can be used.
Example. Check
for primality.
Here , so all prime divisors must have the form
. There are around 1024 numbers less than
65537 of this form, but I only need to check numbers up to the square
root
. (For if a number has a prime
factor, it must have a prime factor less than its square root.)
(The next value of is 257, which is larger than
.) Conclusion: 65537 must be prime!
Proposition. for
.
Proof. and
, so
. The result is true for
.
Take , and assume the result is true for n; I'll try to
prove it for
. By assumption,
Now
That is,
This is the statement for , so the proof is complete, by
induction.
Proposition. If ,
.
Proof. Assume (if not, switch m
and n). Suppose p is prime and
and
. Also,
since
implies that
occurs in this
product. But
Since p divides both of the terms on the right, , so
. This is impossible, since all
the
's are odd.
Therefore, there is no prime dividing both and
, and hence
.
Copyright 2019 by Bruce Ikenaga