8.3 PROJECT

FERMAT AND MERSENNE PRIMES

In Section 8.3, you learned about Fermat's Little Theorem and testing whether numbers are prime. In this project, you will explore two special types of numbers and test whether they are prime.

Very large prime numbers play a vital role in keeping information secure. There are two special types of numbers that have played a role in searching for large primes. They are called Fermat numbers and Mersenne numbers. A Fermat number is a number of the form $2^{2^n}+1$, where $n=0,1,2,\dots$. For example, when $n=2$, we have the Fermat number $2^{2^2}+1=2^4+1=17$. Since this resulting number is prime, we say that $17$ is a Fermat prime.

1. Find the Fermat numbers that correspond to $n=0$, $n=1$, and $n=3$. Are these numbers Fermat primes? (Note that the Fermat number $\mathrm{65,537}$, which corresponds to $n=4$, is a Fermat prime.)

2. Find the Fermat number that corresponds to $n=5$.

3. Evaluate the expression $\left(2^9+2^7+1\right)\left(2^{23}-2^{21}+2^{19}-2^{17}+2^{14}-2^9-2^7+1\right)$. Is the Fermat number that corresponds to $n=5$ a prime number? Why or why not?

A Mersenne number is a number of the form $2^p-1$, where p is a prime number. If the result is a prime, then the number is a Mersenne prime.

It is generally unknown which Fermat numbers and which Mersenne numbers are prime. It is believed that only the Fermat numbers corresponding to $n=0,1,2,3$, and $4$ are prime and infinitely many Mersenne numbers are prime. In fact, since 1996, the Great Internet Mersenne Prime Search (GIMPS) has been testing larger and larger Mersenne numbers to determine which ones are prime. This collaborative effort uses the computing power of multiple volunteer computers connected to the internet and led to the discovery, in December 2018, of the largest known prime number, $2^{\mathrm{82,589,933}}-1$, which has $\mathrm{24,862,048}$ digits.

4. Find the Mersenne numbers that correspond to $p=2$, $p=3$, $p=5$, and $p=7$. Determine whether these are Mersenne primes.

5. Find the Mersenne number that corresponds to $p=11$.

Recall that the contrapositive of Fermat's Little Theorem is stated as follows:

Let x and n be positive integers. If $x^n-x\not\equiv 0\left(modn\right)$, then n is not a prime number.

6. Use the contrapositive of Fermat's Little Theorem to show that the Mersenne number corresponding to $p=11$ is not a Mersenne prime. (Hint: Rewrite the exponent as a sum of powers of $2$.)

7. Find a prime factorization for the Mersenne number in the previous problem. How did you approach factoring it?