Test di Lucas-Lehmer
Il test di Lucas-Lehmer è una verifica della primalità dei primi di Mersenne. In sintesi, per numero primo, detto il -esimo numero di Mersenne, esso è primo se e solo se divide , dove è l'n-esimo termine della successione definita ricorsivamente come:
a partire da
Il test è stato sviluppato originariamente dal matematico Édouard Lucas nel 1870 e semplificato da Derrick Norman Lehmer nel 1930. Il test è talmente rapido e facile da programmare, che nel 1978 due studenti delle superiori dimostrarono che il numero di Mersenne è primo, battendo il precedente record del più grande numero primo allora conosciuto.
È possibile anche un'ottimizzazione nel tempo di calcolo, per poter trattare numeri maggiori, dato che cresce molto velocemente, all'aumentare di , per diventare presto intrattabile. Si può sostituire, alla successione precedente, quella specifica per il numero da verificare , ricavata come segue:
dove mod è il modulo, ossia il resto della divisione per . Questa successione ha però lo svantaggio di essere utile solo per i numeri di Mersenne minori o uguali a .
Enunciato
Sia p un numero primo. Il corrispondente numero di Mersenne è primo se e solo se:
Osservazione
Non è restrittivo considerare i numeri di Mersenne con primo anziché con numero naturale. Si dimostra infatti che se è composto, allora anche lo è.
Dimostrazione
![Abbozzo matematica](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)
Per la sufficienza: siano e . È facile allora mostrare per induzione che
Poiché divide , esiste un intero tale che
ossia
Moltiplicando per , ottengo
Elevando al quadrato
Procediamo per assurdo. Supponiamo che sia composto e prendiamo un suo divisore d minore della sua radice quadrata. Sia G il gruppo dei numeri nella forma che sono anche invertibili: G ha al più elementi. Se riscriviamo la 1 e la 2 modulo d, otteniamo e rispettivamente. Quindi u è un elemento di G di periodo . Dato che il periodo di un elemento può al massimo essere pari al numero degli elementi del gruppo, abbiamo la seguente disuguaglianza
Dato che abbiamo una contraddizione, non ha divisori, e dunque è primo.
Voci correlate
- Test di Lucas-Lehmer-Riesel
- Algoritmo AKS
- Fattorizzazione
- Resto di Lucas-Lehmer
- Test di primalità
- Test di Miller - Rabin
- Test di Fermat
Collegamenti esterni
- (EN) Dimostrazione del test di Lucas-Lehmer (PDF), su 140.122.140.53. URL consultato l'8 agosto 2005 (archiviato dall'url originale il 16 giugno 2006).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)