Fermat and Mersenne Primes

 

Fermat primes

Numbers of the form $F_n=2^{2^n}+1$ were studied by the outstanding French Mathematician Pierre de Fermat and are called Fermat Numbers.The first five Fermat Numbers are $F_0=3,F_1=5,F_2=17,F_3=257$ and $F_4=65537$

In order to find specific examples of primes, it seems reasonable to look at integers of the form $2^m \pm 1$, since many small primes such as $3,5,7,17,31\ldots$ have this form

If $2^m+1$  is prime then $m=2^n$ for some integers $n \ge 0$

Proof:we prove the contra positive that $m$ is not a power of 2 then $2^m + 1$ is not prime.If $m$ is not a power of 2, then $m$ has the form $2^nq$  for some odd $q>1$.Now the polynomial $f(t)=t^q+1$ has a root $t=-1$.So it is divisible by $t+1$.This is a proper factor since $q >1$, so putting $t=x^{2^n}$ we see that the polynomial $g(x)=f(x^{2^n})=x^m+1$ has a proper factor $x^{2^n}+1$.taking $x=2$ we see that $2^{2^n} +1$ is a proper factor of the integer $g(2)=2^m +1$, which cannot therefore be prime. 

Numbers of the form $F_n=2^{2^n}+1$ are called Fermat Numbers, and those which are prime are called Fermat Primes.Fermat conjectured that $F_n$ is prime for every $n \ge 0$. For $n=0,\ldots , 4$, the numbers $F_n=3,5,17,257,65537$ are indeed prime.But in 1732 Euler showed that the next Fermat number 

$$F_5=2^{2^5}+1=4294967297=641 \times 6700417$$ 

is composite.The Fermat numbers have been studied intensively, often with the aid of computers, but no further Fermat primes have been found. It is conceivable that there are further Fermat primes (perhaps infinitely many) which we have not yet found, but the evidence is not very convincing. These primes are important in geometry: in 1801 Gauss showed that a regular polygon with $k$ sides can be constructed by ruler-and-compass methods if and only if $k=2^ep_1\ldots p_r$, where $p_1..... p_r$, are distinct Fermat primes.

Lemma: Distinct Fermat Numbers $F_n$ are mutually coprime.

Proof:

Let $d=gcd(F_n,F_{m})$ be the greatest common divisors of two Fermat numbers $F_n$ and $F_{m}$.($F_n = 2^{2^n} + 1$ and $F_m = 2^{2^m} + 1$, where $m$ and $n$ are positive integers).Lets assume that $d>1$.

The difference between $F_n​$ and $F_m$​ is: $F_n​−F_m​=(2^{2^n}+1)−(2^{2^m}+1)$ 

$=2^{2^n}−2^{2^m}$

Now, let's factor out $2^{2^m}:$

$=2^{2^m}(2^{2^{n−m}}−1)$

This is an even number and $d$ must divide this.

It is  noted that $d$ must also divide $2^{2^m}+1$ which is an odd number.This shows that the initial assumption $d>1$ cannot  satisfied and hence $d=1$.ie; $F_n$ and $F_m$ are co prime.

Mersenne Primes

Theorem:if $m>1$ and $a^m-1$ is prime, then $a=2$  and $m$ is prime.

Proof:

1.Assume $2^p−1$ is prime, where $p$ is a positive integer.

2.If $p$ is composite (i.e., not prime), then it can be expressed as $p=ab$, where $a$ and $b$ are integers greater than 1. Since $p$ is composite, neither $a$ nor $b$ can equal 1 or $p$. Thus, both $a$ and $b$ must be less than $p$.

3.Consider the factorization of  $2^p-1$

$2^p-1=(2^{p/2}+1)(2^{p/2}−1)$

4.Since $p$ is prime, $2^{p/2}+1$ and $2^{p/2}−1$ are integers greater than 1 and less than $2^p−1$. Therefore, both $2^{p/2}+1$ and $2^{p/2}−1$ cannot divide $2^{p−1}$ entirely.

5. It is also noted that 
$2^p−1$ cannot be prime if $p$ is composite.

6.If $p$ is prime, then $2^p−1$ remains irreducible, as both factors $2^{p/2}+1$ and $2^{p/2}−1$ are smaller than $2^p−1$ and cannot divide it.

7.Thus, if $2^p−1$ is prime, then $p$ must also be prime.

This completes the proof

Integers of the form $2^p-1$,where $p$ is prime, are called Mersenne numbers, after Mersenne who studied them in 1644; those which are Prime are called Mersenne Primes.

For the primes $p=2,3,5,7$, the Mersenne Numbers

$$M_p=3,7,31,127$$

are indeed Prime. But $M_{11}=2047=23*89$. So $M_p$ is not prime for every prime $p$.

Visit https://www.mersenne.org/ to know more about the latest Mersenne Primes.As in the case of Fermat Primes, it is not known whether there are finitely or infinitely many Mersenne Primes.

Significance: Mersenne primes have practical applications in cryptography and computer science, particularly in the field of primality testing and in the development of efficient algorithms for encryption and data security.

Challenges: Finding Mersenne primes becomes increasingly difficult as $p$ grows larger. The Lucas-Lehmer primality test is commonly used to determine whether a Mersenne number is prime, but it's computationally intensive for large values of $p$.

In summary, Mersenne primes represent a captivating aspect of number theory and have practical implications in various fields, including cryptography and computer science. Their properties continue to inspire research and exploration in mathematics.