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

modifica

Sia p un numero primo. Il corrispondente numero di Mersenne   è primo se e solo se:

 

Osservazione

modifica

Non è restrittivo considerare i numeri di Mersenne   con   primo anziché   con   numero naturale. Si dimostra infatti che se   è composto, allora anche   lo è.

Dimostrazione

modifica

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

modifica

Collegamenti esterni

modifica
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica