RE: O maior numero primo do mundo

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Mon, 31 May 1999, Alexandre Stauffer wrote:

> > > > teste de Lucas-Lehmer
> > > Em que consiste o teste de primalidade de Lucas-Lehmer???
> 
> > Para verificar se 2^p - 1 é primo defina:
> > a(0) = 4, a(n+1) = (a(n)^2 - 2) mod (2^p - 1).
> > Teorema: 2^p - 1 é primo se e somente se a(p-2) = 0 (mod 2^p - 1).
> 
> Certo....
> 
> este teorema retorna resultado 100% correto????

Oops, faltou dizer que p > 2. Mas fora este caso trivial, sim.
Todo teorema é 100% correto, por definição de teorema.
Há uma demonstração completa em http://www.utm.edu/research/primes/,
aliás uma excelente home page sobre números primos.
Segue abaixo a demonstração chupada do livro que o Gugu e eu estamos
acabando de escrever. Em LaTeX, espero que seja legível.
Vocês também podem ver uma versão *incompleta* do livro em
http://www.mat.puc-rio.br/~nicolau/qwerty/mersenne
(o teste de Lucas-Lehmer já está lá).

=============================================================================

{\nobf Teorema 3.12:}
{\sl Seja $s$ a seqüência definida por $s(0) = 4$,
$s(k+1) = (s(k))^2 - 2$ para todo natural $k$.
Seja $n > 2$; $M_n = 2^n - 1$ é primo se e somente se
$s(n-2)$ é múltiplo de $M_n$.}

{\nobf Dem: }
Observemos inicialmente que
$$s(n) = (2+\sqrt{3})^{2^n} + (2-\sqrt{3})^{2^n}$$
para todo natural $n$.
A demonstração por indução é simples:
claramente $s(0) = 4 = (2+\sqrt{3})^{2^0} + (2-\sqrt{3})^{2^0}$ e
\begin{align}
s(k+1) &= (s(k))^2 - 2 \notag\\
&= ((2+\sqrt{3})^{2^k} + (2-\sqrt{3})^{2^k})^2 - 2 \notag\\
&= ((2+\sqrt{3})^{2^k})^2 + 2 \cdot (2+\sqrt{3})^{2^k} \cdot
(2-\sqrt{3})^{2^k} 
+ ((2-\sqrt{3})^{2^k})^2 - 2 \notag\\
&= (2+\sqrt{3})^{2^{k+1}} + (2-\sqrt{3})^{2^{k+1}}.\notag
\end{align}

Suponha por absurdo que
$M_n | (2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}}$
e que $M_n$ seja composto, com um fator primo $q$ com $q^2 < M_n$.
Teremos $(2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}} \equiv 0 \pod q$
donde, no grupo multiplicativo $G = (\ZZ/(q) [\sqrt{3}])^\ast$, temos
% conidrin lactente 2 gotas 4x por dia
$(2+\sqrt{3})^{2^{n-2}} = - (2-\sqrt{3})^{2^{n-2}}.$
Como $2 - \sqrt{3} = (2 + \sqrt{3})^{-1}$ esta equação pode ser reescrita
como $(2+\sqrt{3})^{2^{n-1}} = -1$ (ainda em $G$),
o que significa que a ordem de $2+\sqrt{3}$ em $G$ é exatamente $2^n$.
Isto é um absurdo, pois o número de elementos de $G$ é apenas $q^2 - 1 <
2^n$.
Fica portanto demonstrado que se $s(n-2)$ é múltiplo de $M_n$
então $M_n$ é primo.

Suponha agora $M_n$ primo, $n > 2$. Lembramos que $n$ é um primo ímpar.
Por reciprocidade quadrática temos
$(\frac{3}{M_n}) = - (\frac{M_n}{3}) = -1$,
pois $3 \equiv M_n \equiv -1 \pod 4$ e $M_n \equiv 1 \pod 3$.
Assim, 3 não é um quadrado em $\ZZ/(M_p)$ e
$K = \ZZ/(M_p)[\sqrt{3}]$ é um corpo de ordem $M_n^2$.
Queremos provar que 
$(2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}} \equiv 0 \pod M_p$,
ou seja, que é igual a 0 em $K$.
Isto equivale a demonstrarmos que temos
$(2+\sqrt{3})^{2^{n-2}} = - (2-\sqrt{3})^{2^{n-2}}$ em $K$,
o que pode ser reescrito como $(2+\sqrt{3})^{2^{n-1}} = -1$;
devemos portanto provar que a ordem de $2+\sqrt{3}$ é exatamente $2^n$.
Note que $2^n = M_n + 1$ donde
$(2 + \sqrt{3})^{2^n} = (2 + \sqrt{3})^{M_n} (2 + \sqrt{3}) =
(2 - \sqrt{3}) (2 + \sqrt{3}) = 1$;
assim é claro que a ordem de $2 + \sqrt{3}$ é um divisor de $2^n$.

Como $K^\ast$ tem $M_n^2 - 1 = 2^{n+1}(2^{n-1} - 1)$ elementos,
devemos provar que $2 + \sqrt{3}$ não é uma quarta potência em $K$.
Note que $(2 + \sqrt{3})^{2^n} = 1$ demonstra que $2 + \sqrt{3}$
é um quadrado, o que aliás pode ser visto mais diretamente:
$2 + \sqrt{3} = (1 + \sqrt{3})^2/2$
e $2 = 2^{n+1} = 2^{(n+1)^2}$ é uma quarta potência em $K$.
Resta-nos assim demonstrar que $\pm(1 + \sqrt{3})$ não são quadrados em
$K$.
Suponha por absurdo que
$\epsilon (1 + \sqrt{3}) = (a + b \sqrt{3})^2$, com $\epsilon = \pm 1$;
temos $\epsilon (1 - \sqrt{3}) = (a - b \sqrt{3})^2$
e, multiplicando, $-2 = (a^2 - 3 b^2)^2$,
o que significa que $-2$ é um quadrado módulo $M_n$
(pois $a$ e $b$ são inteiros).
Isto, entretanto, é claramente falso:
$(\frac{-2}{M_n}) = (\frac{-1}{M_n}) (\frac{2}{M_n}) = -1 \cdot 1 = -1$,
pois $M_n \equiv 3 \pod 4$ e já vimos que 2 é um quadrado módulo $M_p$.
Isto conclui a demonstração.
\qed