$\newcommand{\Z}{\mathbb Z}$Para um natural $n$, defina
\[
M(n)=2^n-1.
\]
O número $M(n)$ chama-se número de Mersenne. Nós estamos interessados principalmente nos números $M(n)$ que são primos. Se um número de Mersenne é primo, então ele chama-se primo de Mersenne.
Lema. Se $M(n)$ é primo, então $n$ é primo.
Demonstração. Assuma que $n$ é composto e escreva $n=ab$ onde $1<a,b<n$. Ora,
\[
2^n-1=(2^a)^b-1=(2^a-1)((2^a)^{b-1}+(2^a)^{b-2}+\cdots+2^a+1)
\]
e $2^n-1$ não é primo.
Exemplo. Considerando os números de Mersenne $M(p)$ para os primeiros primos $p$, obtemos que $M(2)=3$, $M(3)=7$, $M(5)=31$, $M(7)=127$ são primos mas $M(11)=2047=23\cdot 89$ é composto.
O seguinte resultado, devido a Fermat, dá um critério para os possíveis primos que podem dividir um número de Mersenne $M(p)$ para algum primo $p$.
Critério de Fermat. Seja $p\geq 3$ um primo e $q$ um fator primo de $M(p)$. Então $q=1+2rp$ com algum inteiro positivo $r$.
Antes de demonstrar o Critério de Fermat, nós vamos estudar um pouco o comportamento das potências de um elemento $\bar a\in\Z_p$ onde $p$ é um primo. Seja $\bar a\in\Z_p$ diferente de $\bar 0$ e considere a sequência
\[
\bar a^0=\bar 1,\bar a,\bar a^2,\bar a^3,\ldots
\]
Pelo Pequeno Teorema de Fermat $\bar a^{p-1}=\bar 1$ e isso garante que o elemento $\bar 1$ aparece na sequência na última linha destacada. Assuma que $m\geq 1$ é o menor inteiro tal que $\bar a^m=\bar 1$. Nós vamos chamar $m$ o período do elemento $\bar a$ (alguns livros chamam este número a ordem de $\bar a$).
Observações.
- Os elementos $\bar a^0,\bar a^1,\ldots,\bar a^{m-1}$ são mutualmente distintos. Pois, se existisse $1<i<j<m-1$ tal que $\bar a^i=\bar a^j$, então teríamos que $\bar a^{j-i}=\bar a^j/\bar a^i=\bar 1$, mas neste caso $0<j-i<m$ e isso contradiz ao fato que $m$ é o menor inteiro com $m\geq 1$ e $\bar a^m=\bar 1$.
- A sequênca das potências
\[
\bar a^0=\bar 1,\bar a,\bar a^2,\bar a^3,\ldots
\]
é periódica e o período dela é precisamente $m$. De fato, observe, pela observação anterior, que os termos
\[
\bar a^0=\bar 1,\bar a,\ldots,\bar a^{m-1}
\]
são mutualmente distintos, depois $\bar a^m=\bar 1$, $\bar a^{m+1}=\bar a$, $\bar a^{m+2}=a^2$, e deste ponto a sequência vai se repetir. - Temos pelas duas observações acima que se $\bar a^k=\bar 1$ para algum $k\geq 0$, então $k$ é um múltiplo do período $m$.
- Pelo Pequeno Teorema de Fermat, $\bar a^{p-1}=\bar 1$, então o período $m$ do elemento $\bar a\in\Z_p\setminus\{0\}$ é um divisor de $p-1$.
- Um elemento $\bar a\in\Z_p\setminus\{\bar 0\}$ é primitivo se e somente se seu período é $p-1$.
A segunda observação explica porque chamamos o número $m$ o período de $\bar a$.
Demonstração (Critério de Fermat). Assuma que um primo $q$ divide $2^p-1$. Então $2^p\equiv 1\pmod q$ que implica que $\bar 2^p=\bar 1$ em $\Z_q$. Pelas observações acima, temos que o período de $\bar 2$ em $\Z_q$ é um divisor de $p$. Como $p$ é um primo e o período de $\bar 2$ não é $1$, temos que $\bar 2$ tem período $p$. Mas o período de $2$ é um divisor de $q-1$, então temos que $p$ divide $q-1$; ou seja $q=r’p+1$. Agora observe que $q$ e $p$ são ímpares, então $r’p$ precisa ser par e $r’p$ pode ser escrito como $2rp$ com $r=r’/2$. Logo $q=2rp+1$ como foi afirmado.
Exemplo. Como foi observado, $M(11)=2047=23\cdot 89$ e note que $23=2\cdot 11+1$ enquanto $89=8\cdot 11+1$ e os dois fatores primos de $M(11)$ são de fato na forma $2rp+1$.
O Critério de Fermat é útil para verificar se $M(p)$ é primo ou composto para um primo $p$ moderado. Para primos maiores, nós utilizaremos o Teste de Lucas–Lehmer. Como o resultado não é tão elementar, nós vamos apresentar este teste sem demonstração. Defina a sequência $S_k$ recursivamente como
\[
S_0=4\quad \mbox{e}\quad S_{k+1}=S_k^2-2 \mbox{ para }k\geq 0.
\]
Teorema (Lucas-Lehmer). Se $p$ é um primo, então $M(p)$ é primo se e somente se $S_{p-2}\equiv 0\pmod{M(p)}$.
Lembre que pelo Teorema de Euclides, existem infinitos primos, mas sempre existe um maior primo conhecido. Neste momento o maior primo conhecido é o primo de Mersenne $M(82.589.933)=2^{82.589.933} − 1$. Este é um número de $24,862,048$ dígitos, e foi descoberto em dezembro de 2018. Existe uma pesquisa comunitária com o objetivo de encontrar um primo de Mersenne maior. O projeto atualmente (outubro de 2020) oferece um prémio de 3000 dólares americanos para a descoberta de um primo maior que $M(82.589.933)$. Na pesquisa destes primos, uma versão mais elaborada do Algoritmo de Lucas-Lehmer está usada.
É conjeturado por matemáticos que existem infinitos primos de Mersenne e também que existem infinitos primos $p$ tal que $M(p)$ é composto, mas neste momento ninguém sabe como provar estas afirmações.