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
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,
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 .
Bruce Ikenaga's Home Page
Copyright 2019 by Bruce Ikenaga