Prova de Lucas-Lehmer per a nombres de Mersenne: diferència entre les revisions
Contingut suprimit Contingut afegit
m Tipografia |
m Gestió de l'entitat NBSP |
||
Línia 110:
\end{array}</math>
Ara se suposa que ''M''<sub>''p''</sub> és compost amb un factor primer no trivial ''q''
:<math>(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}</math>.
Com que ''q''
Ara, com que <math>M_p \equiv 0 \pmod q</math>, i <math>\omega \in X</math>, es té <math>kM_p\omega^{2^{p-2}} = 0</math> de ''X'', el qual per l'equació (1) dona <math>\omega^{2^{p-1}} = -1</math>. Elevant al quadrat tots dos cantons dona <math>\omega^{2^p} = 1</math>, que mostra que <math>\omega</math> és invertible i la seva inversa és <math>\omega^{2^{p}-1}</math> i per tant pertany a ''X''*, i a més té un [[ordre (teoria de grups) ordre]] que divideix <math>2^p</math>. De fet l'ordre ha de ser igual a <math>2^p</math>, donat que <math>\omega^{2^{p-1}} \neq 1</math> i per tant l'ordre no divideix a <math>2^{p-1}</math>. Com que l'ordre d'un element és com a màxim l'ordre (mida) del grup, s'arriba a la conclusió de què <math>2^p \leq q^2 - 1 < q^2</math>. Però com que ''q'' és un factor primer no trivial de <math>M_p</math>, ha de ser <math>q^2 \leq M_p = 2^p-1</math>, que dona la contradicció <math>2^p < 2^p-1</math>. Per tant <math>M_p</math> és primer.
| |||