Dato un numero di Mersenne Mp=2p-1, con p primo >2, si ha: Mp è primo  Sp-1  0 (mod Mp) Dimostrazione

Teoria dei numeri

Lezione del giorno 12 maggio 2008

Le tecniche per verificare se un numero di Mersenne è primo fanno uso del cosiddetto criterio di Lucas-Lehmer, che ora esporremo.

Definiamo la seguente successione Sn di numeri naturali:

S1 = 4; per ogni i>1 Si = Si-12-2

(quindi per esempio S2=4²-2=14, S3=14²-2=194 etc.) Teorema di Lucas-Lehmer.

Dato un numero di Mersenne Mp=2^p-1, con p primo >2, si ha:

Mp è primo  Sp-1  0 (mod Mp) Dimostrazione:

(): Poniamo m=Mp=2^p-1, e supponiamo m primo.

Costruiamo l’insieme A di tutte le espressioni formali [a]+[b], dove [a],[b]Zm e dove 2 espressioni [a]+[b], [c]+[d] si considerano uguali quando [a]=[c], [b]=[d] in Zm .

Definiamo in A due operazioni di somma e prodotto, con le usuali regole algebriche (tenendo conto che i coefficienti si sommano e moltiplicano in Zm ) e con la regola che ²=[3] (in pratica  si comporta come la “radice quadrata” di [3]).

E’ facile verificare che A rispetto a tali operazioni è un anello commutativo con unità, ed inoltre (identificando ogni [a]Zm con [a]+[0]) si può pensare Zm sottoanello di A.

Considerati gli elementi =[2]+[1], ω=[2]+[-1] in A, e posto per ogni naturale n>0:

Ln = _ω^(2n-1)_ω^(2n-1) si ha Ln = [Sn] per ogni n.

Dimostriamolo per induzione su n.

Per n=1 si ha L1 = +^ω= [4] = [S1].

Supponiamo che sia Ln = [Sn] .

Tenendo conto che ^ω=[4]-[1]² = [1], si ha:

Ln+1 = _ω⁽²ⁿ⁾_ω⁽²ⁿ⁾= _ω⁽²ⁿ⁾_ω⁽²ⁿ⁾+2_ω^(2n-1)_ω^(2n-1)-[2] == (ω^(2n-1) ω^(2n-1))²-[2] = Ln2- [2] =

= [Sn2- 2] = [Sn+1] .

Calcolando, con la regola di Newton, la potenza ([1]+[1])^m in A si ottiene:

([1]+[1])^m = ^{i m i}

m

0 i

α i [1]

m _

 

 



 (*)

Ma per ogni i tale che 1im-1, si ha _



 



 i

m =_i!(m^m!_1)! dunque i!(m-1)! _



 



 i

m = m!, ossia il

numero primo m è divisore del prodotto i!(m-1)! _



 



 i

m , e poiché m non è divisore né di i! né di (m-

1)! (che sono prodotti di fattori <m, dunque non multipli di m), si ha che m è divisore _



 



 i

m , ossia nella sommatoria (*) si annullano tutti gli addendi (tenendo conto che [m]=[0] in Zm) tranne che per i=1, i=m, ottenendo così:

([1]+[1])^m = [1] + ^m = [1] + [3]^(m-1)/2 (tenendo conto che ²=[3]).

Calcoliamo i simboli di Legendre (3/m), (2/m) (si ha 2,3<m dunque 2,3 non sono multipli di m).

Si ha, essendo p=2k+1 dispari:

m = 2^p-1 = 4^k2-1  1^k2-1 =1=1² (mod 3)

quindi m è un resto quadratico modulo 3, (m/3)=1, e per la legge di reciprocità quadratica:

(3/m) = (-1)(3-1)(m-1)/4(m/3) = (-1)^(m-1)/2(m/3) = -(m/3) = -1 (perché (m-1)/2=2^p-1-1 è dispari).

Per quanto riguarda (2/m), osservando che m = 2^p-1 7 (mod 8) (perché 2^p=2^2k+1=4^k2 è multiplo di 8), per una regola già dimostrata si ha (2/m)=1.

In particolare per il criterio di Eulero si avrà:

2^(m-1)/2  1 (mod m) 3^(m-1)/2  -1 (mod m) (*)

In particolare [3]^(m-1)/2=[-1] in Zm , dunque ([1]+[1])^m = [1] + [-1].

Moltiplicando ambo i membri per [1] + [1] si ottiene:

([1]+[1])^m+1 = ([1] + [-1])( [1] + [1]) = [1]²-[1]²² = [1]-[3] = -[2]

Poiché ([1]+[1])² = [1]²+[1]²²+2[1]=[4]+[2]=[2], si ha ([2])^(m+1)/2=-[2].

Ma da (*) si deduce che [2]^(m-1)/2=[1], quindi, essendo (m+1)/2=[(m-1)/2]+1, si ha [2]^(m+1)/2=-[2].

Essendo 2,m coprimi (perché m è dispari), [2] è invertibile in Zm , e moltiplicando ambo i membri dell’ultima eguaglianza per l’inverso di [2] si ottiene ^(m+1)/2=-[1].

Ma (m+1)/2=2^p-1 quindi _ω^2p1 _ω^2p2_ω^2p2 =-[1] e moltiplicando ambo i membri per _ω^2p2 (sempre tenendo conto che ^ω=[4]-[1]² = [1] ) si ottiene _ω^2p2 _ω^2p2, [0]=ω^2p2 ω^2p2 Lp-1, ed essendo Ln = [Sn] per ogni n si conclude che [Sp-1]=[0] ossia la tesi Sp-1  0 (mod m).

(): Per assurdo supponiamo Mp=2^p-1 non primo, quindi esiste un suo divisore non banale t ^Mp , e se m è un fattore primo di t, si ha che m è divisore di Mp , con m Mp ; inoltre m è dispari, perché lo è Mp.

Costruiamo l’anello A esattamente come nella dimostrazione della prima implicazione (anche se nel nostro caso m è un primo divisore di Mp, e non coincide con Mp), ed anche gli elementi , ω in A, e la successione Ln tale che Ln = [Sn] per ogni n. Essendo per ipotesi Sp-1  0 (mod Mp), si ha a maggior ragione Sp-1  0 (mod m), quindi [0]=[Sp-1]=Lp-1=ω^2p2 ω^2p2, ω^2p2 ω^2p2.

Se ripercorriamo all’inverso gli ultimi passaggi della dimostrazione della prima implicazione, moltiplicando ambo i membri per _ω^2p2 e tenendo conto che ω = [1], si ottiene:

_ω^2p1 _ω^2p2_ω^2p2 =-[1] da cui quadrando _ω^2p _[1].

Notiamo che la cardinalità dell’anello A è m², essendo un elemento generico di A dipendente da una coppia di elementi in Zm .

Sia s il periodo di  nel gruppo moltiplicativo A* degli elementi invertibili di A rispetto al prodotto:

si ha sA*A-{0}=A-1 = m²-1, dunque s<m².

Ma essendo _ω^2p _[1], s è divisore di 2^p, dunque s=2^r con rp. Affermiamo che r=p: se per assurdo fosse r<p, si avrebbe rp-1, e inoltre –[1] = ω^2p1 (ω^2r)^2p1r=[1], da cui 1-1 (mod m), contraddizione perché m è primo dispari.

Dunque è vero che r=p, e che s=2^p. Ma allora 2^p=s<m² ( Mp )²=Mp=2^p-1, contraddizione.

Il Teorema di Lucas-Lehmer fornisce un test deterministico di primalità per i numeri di Mersenne:

verifichiamo che esso ha complessità polinomiale.

Notiamo prima di tutto che il numero Mp=2^p-1 rappresentato in base 2 è formato da p cifre tutte eguali a 1: dunque la sua lunghezza binaria è proprio p.

Per la verifica della condizione Sp-1  0 (mod Mp) basta costruire le riduzioni modulo Mp dei termini S1,S2,….,Sp-1 (ognuno ottenuto dal precedente secondo la formula Si = Si-12-2), e verificare se l’ultima riduzione (di indice p-1) è 0.

Il calcolo di ognuna di tali riduzioni modulo p coinvolge il calcolo del quadrato della precedente e una divisione per Mp con una complessità di ordine O(p²) (essendo p la lunghezza binaria di Mp).

Poiché il numero delle riduzioni da calcolare è <p, in totale l’algoritmo ha complessità di ordine polinomiale O(p³).

Anche nel caso in cui il numero di Mersenne Mp non sia primo, i fattori primi di Mp hanno una struttura particolare:

Teorema.

Se p è un primo >2, per ogni fattore primo q di Mp=2^p-1 si ha q1 (mod p), quindi q=1+kp con k naturale (e in particolare k pari), e inoltre si ha q1,7 (mod 8).

Dimostrazione:

Essendo Mp dispari, si ha q>2, quindi q dispari. Poiché 2^p^{1 (mod Mp}), anche 2^p^{1 (mod q),}

dunque [2]^p=[1] in Zq* e se s è il periodo di [2] in Zq*, si ha sp, da cui, essendo p primo, s=p (perché s1 in quanto [2][1]).

Il periodo s=p è divisore della cardinalità q-1 di Zq* , dunque q1 (mod p), q=1+kp con k naturale (e in particolare k pari perché q,p sono dispari).

Infine, posto k=2t, [2]^(q-1)/2=([2]^p)^t=[1] in Zq* , 2^(q-1)/21 (mod q), e per il criterio di Eulero 2 è resto quadratico modulo q, dunque (2/q)=1, e ciò avviene solo per q1,7 (mod 8).

Per trovare un fattore primo di Mp (con p primo >2 fissato), si può procedere allora facendo assumere in successione al parametro t i valori interi positivi t=1,2,…., e verificando con l’algoritmo della divisione se il numero q=1+2tp è 1,7 (mod 8) ed è divisore di Mp. Il minimo valore di t per cui q=1+2tp è divisore di Mp fornisce con certezza un valore primo q (se q non fosse primo avrebbe un divisore primo q1<q, ma q1 sarebbe a maggior ragione divisore di Mp, quindi sarebbe della forma q1=1+2t1p con t1<t, contro la minimalità di t).

Dopo avere trovato un fattore primo q di Mp, si può ripetere il ragionamento sul numero Mp/q per trovare altri fattori primi di Mp e pervenire alla completa fattorizzazione di Mp in prodotto di primi.

Numeri perfetti.

Un numero naturale n>1 è detto perfetto se n è la somma dei suoi divisori <n.

Per esempio n=6 è perfetto in quanto 6=1+2+3; n=8 non è perfetto in quanto 81+2+4.

Se per ogni naturale n definiamo la funzione (n) uguale alla somma di tutti i divisori di (incluso n), si ha che un naturale n>1 è perfetto se e solo se (n)=2n.

Se n è un naturale >1, e se la fattorizzazione di n in prodotto di potenze di primi distinti è:

n=p₁^k1p₂^k2....p_r^{kr (pi} primi distinti, ki>0)

allora (per la fattorizzazione unica) ogni divisore d di n ha la forma:

d=p₁^h1p₂^h2....p_r^hr con 0 hi ki per ogni i=1,….,r dunque si ha la seguente formula per il calcolo di (n):

(n)= ^



 r k h 0i1

rh 2h 1h

i i

r 2 1p ....p p

Teorema.

Se n,m sono naturali >1 coprimi, si ha (nm)=(n)(m).

Dimostrazione:

Se le fattorizzazioni di n,m in prodotto di potenze di primi distinti sono rispettivamente:

n=p₁^k1p₂^k2....p_r^kr m=p_r1^kr1p_r2^kr2....p_s^ks la fattorizzazione di nm in prodotto di potenze di primi distinti è:

nm=p₁^k1p₂^k2....p_r^krp_r1^kr1p_r2^kr2....p_s^ks e per la proprietà distributiva si ottiene:

(n)(m)=  



    ^

i

i i i

s 1 r r

1

k h

0 0 h k

sh 1h

h r h r

1 ....p )( p ....p ) p

( = 



 i i

s 2 1

k h 0

rh 2h

1h p ....p

p =(nm).

Vedremo che vi è uno stretto legame fra la teoria di numeri perfetti e quella dei numeri di Mersenne.

Cominceremo con la dimostrazione del seguente risultato di Euclide: dato il numero di Mersenne primo Mk=2^k-1 (quindi con k primo), il numero naturale n=2^k-1Mk=2^k-1(2^k-1) è perfetto.