title: Test di Lucas-Lehmer
text: # Test di Lucas-Lehmer
  
  Il test di Lucas-Lehmer è una verifica della primalità dei primi di Mersenne. In sintesi, per $p$ numero primo, detto $M_{p}=2^{p}-1$ il $p$-esimo numero di Mersenne, esso è primo se e solo se divide $L_{p-1}$, dove $L_{n}$ è l'n-esimo termine della successione definita ricorsivamente come:
  
      $L_{n+1}=L_{n}^{2}-2$
  
  a partire da
  
      $L_{1}=4$
  
  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 $2^{21701}-1$ è 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 $L_{n}$ cresce molto velocemente, all'aumentare di $n$, per diventare presto intrattabile. Si può sostituire, alla successione precedente, quella specifica per il numero da verificare $M_{n}$, ricavata come segue:
  
      $L_{n+1}\equiv (L_{n}^{2}-2)\,\operatorname {mod} \,M_{p}$
  
  dove mod è il modulo, ossia il resto della divisione per $M_{p}$. Questa successione ha però lo svantaggio di essere utile solo per i numeri di Mersenne minori o uguali a $M_{p}$.
  
  ## Enunciato
  
  Sia p un numero primo. Il corrispondente numero di Mersenne $M_{p}=2^{p}-1$ è primo se e solo se:
  
      $L_{p-1}\equiv 0\,\operatorname {mod} \,M_{p}$
  
  ## Osservazione
  
  Non è restrittivo considerare i numeri di Mersenne $M_{p}$ con $p$ primo anziché $M_{n}$ con $n$ numero naturale. Si dimostra infatti che se $n$ è composto, allora anche $M_{n}$ lo è.
  
  ## Dimostrazione
  
  Per la sufficienza: siano $u=2+{\sqrt {3}}$ e $v=2-{\sqrt {3}}$. È facile allora mostrare per induzione che
  
      $L_{n}=u^{2^{n-1}}+v^{2^{n-1}}$
  
  Poiché $M_{p}$ divide $L_{p-1}$, esiste un intero $R$ tale che
  
      $L_{p-1}=R\,M_{p}$
  
  ossia
  
      $u^{2^{p-2}}+v^{2^{p-2}}=R\,M_{p}$
  
  Moltiplicando per $u^{2^{p-2}}$, ottengo
  
      $1)\,\,\,\,\,u^{2^{p-1}}=R\,M_{p}u^{2^{p-2}}-1$
  
  Elevando al quadrato
  
      $2)\,\,\,\,\,u^{2^{p}}=\left(R\,M_{p}u^{2^{p-2}}-1\right)^{2}$
  
  Procediamo per assurdo. Supponiamo che $M_{p}$ sia composto e prendiamo un suo divisore d minore della sua radice quadrata. Sia G il gruppo dei numeri nella forma $\left(a+b{\sqrt {3}}\right)\,\operatorname {mod} \,d$ che sono anche invertibili: G ha al più $d^{2}-1$ elementi. Se riscriviamo la 1 e la 2 modulo d, otteniamo $u^{2^{p-1}}\equiv -1\,\operatorname {mod} \,d$ e $u^{2^{p}}\equiv 1\,\operatorname {mod} \,d$ rispettivamente. Quindi u è un elemento di G di periodo $2^{p}$. Dato che il periodo di un elemento può al massimo essere pari al numero degli elementi del gruppo, abbiamo la seguente disuguaglianza
  
      $2^{p}\leq d^{2}-1<M_{p}=2^{p}-1$
  
  Dato che abbiamo una contraddizione, $M_{p}$ non ha divisori, e dunque è primo.
  
  