Teoria dei numeri Lezione del giorno 14 maggio 2008

Teoria dei numeri

Lezione del giorno 14 maggio 2008

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.

Teorema (Euclide).

Se il numero di Mersenne Mk=2^k-1 è primo, il numero n=2^k-1(2^k-1)=2^kM è perfetto.

Dimostrazione.

Essendo Mk dispari, i numeri 2^k-1, p sono coprimi, e per un risultato precedente si ha:

(n)=(2^k-1)(Mk).

Essendo Mk primo si ha (Mk)=1+Mk=1+(2^k-1)= 2^k.

I divisori di 2^k-1 sono le potenze 2⁰, 2¹, …., 2^k-1, dunque (2^k-1)= 2⁰+2¹+2²+….+2^k-1=2^k-1(dove si è sfruttata l’identità (x-1)(1+x+x²+….+x^k-1)=(x^k-1) per x=2).

In totale si ottiene (n)=2^k(2^k-1)=2[2^k-1(2^k-1)]=2n ed n è perfetto.

Eulero dimostrò un parziale viceversa:

Teorema (Eulero).

Se n è un naturale pari perfetto, allora n è della forma n=2^k-1Mk dove Mk=2^k-1 è un numero di Mersenne primo.

Dimostrazione:

Poiché n è pari, se 2^t (con t>0) è la massima potenza di 2 che divide n, si può scrivere n=2^tm con m dispari.

Poniamo k=t+1>1, in modo che n=2^k-1m.

Essendo m dispari, i numeri 2^k-1, m sono coprimi, e dunque (n)=(2^k-1)(m).

Come nella dimostrazione del Teorema precedente si ha (2^k-1)=2^k-1.

Poiché n è perfetto per ipotesi, si ottiene 2^km=2n=(n)=(2^k-1)(m)=(2^k-1)(m).

Dunque 2^k-1 è divisore del prodotto 2^km; ma 2^k, 2^k-1 sono coprimi (perché consecutivi), quindi 2^k-1 è divisore del fattore m, e si ha m=(2^k-1)M, con M naturale.

Sostituendo si ha: 2^km=2^k(2^k-1)M=(2^k-1)(m), da cui (m)=2^kM.

Si ha allora m+M=(2^k-1)M+M=2^kM=(m).

Essendo m,M entrambi divisori (distinti) di m, ed essendo (m) la somma di tutti i divisori di m, concludiamo che m,M sono gli unici divisori di m (e dunque necessariamente M=1), ossia m è primo ed inoltre:

m=(2^k-1)M=(2^k-1)=Mk, ed n=2^k-1m=2^k-1Mk, come voleva la tesi.

Dai Teoremi di Euclide ed Eulero segue che un naturale pari n è perfetto se e solo se è della forma n=2^k-1(2^k-1) con k naturale >1, e con Mk=2^k-1 numero di Mersenne primo.

Per esempio, per k=2, il numero 2²-1=3 è primo, e si ottiene il numero perfetto n=2(2²-1)=6.

Analogamente per k=3, il numero 2³-1=7 è primo, e si ottiene il numero perfetto n=2²(2³-1)=28.

Per quanto riguarda i numeri perfetti dispari, la questione è tutt’ora aperta: non sono stati trovati numeri perfetti dispari, né è stata trovata una loro caratterizzazione, come nel caso dei perfetti pari.

La caratterizzazione dei numeri perfetti pari induce una corrispondenza biunivoca fra essi e i numeri di Mersenne primi: poiché sono stati trovati 44 numeri di Mersenne primi, altrettanti sono i numeri perfetti pari attualmente conosciuti.

Algoritmo per il calcolo della radice n-esima

Sia dato il numero naturale x (radicando), e, fissato un numero naturale n>1, costruiamo un algoritmo che, dato in input x, calcoli la parte intera della radice n-esima di x, ossia il più grande intero y tale che yⁿx.

Rappresentiamo x in base 2, e raggruppiamo le cifre binarie a blocchi di n cifre:

x = 12……k

dove ogni i è un blocco di n cifre binarie (aggiungiamo eventualmente degli zeri a sinistra per rendere il blocco 1 di n cifre, e in ogni caso 10).

Si ha ovviamente 0i2ⁿ-1 per ogni i, essendo ogni i un blocco di n cifre binarie che rappresenta un numero intero 0 in base 2.

Escludiamo il caso banale in cui l’input x abbia non più di n cifre (nel qual caso il numero dei blocchi è k=1) perché in tale caso si ha 2ⁿ>x quindi la parte intera della radice n-esima di x è <2 cioè è =1.

Descriviamo il seguente algoritmo che genera 2 successioni di numeri interi 0:

yi , xi (con i=0,1,…,k) 1) Si pone y0=x0=0

2) Per i=1,….,k si ripete il seguente blocco di istruzioni:

a) Si calcola la massima cifra binaria {0,1} tale che (2yi-1+)ⁿ2ⁿxi-1+i

b) Si pone yi=2yi-1+, xi=2ⁿxi-1+i

Alla fine l’algoritmo esce con output “yk = parte intera della radice n-esima di x”.

Esaminando l’algoritmo si vede che ad ogni iterazione nel passo 2) il numero xi si ottiene shiftando verso sinistra il numero xi-1 di n cifre binarie e aggiungendo il blocco i : quindi, partendo dal valore iniziale xi=0, è ovvio che alla fine del ciclo si avrà xk=x.

D’altro canto il numero yi si ottiene shiftando verso sinistra il numero yi-1 di 1 cifra binaria e aggiungendo la cifra binaria  trovata nel passo a): quindi le successive cifre binarie  trovate nella iterazione della a) sono proprio le cifre binarie dell’output yk .

Inoltre ad ogni iterazione, esaminando le istruzioni a),b), si nota che yinxi, e in particolare yknxk=x.

Dimostriamo inoltre che per ogni i=1,2,…,k si ha:

(yi+1)ⁿ > xi

Ragioniamo per induzione (I^a forma).

Per i=1 è vero, perché il valore  nella a) è in questo caso =1 (in quanto (2y0+1)ⁿ=12ⁿx0+1=1) dunque y1=2y0+1=1, x1=2ⁿx0+1=1 , 1ⁿ=11.

Supponiamolo vero per i-1, e dimostriamolo vero per i.

Dunque supponiamo che (yi-1+1)² > xi-1 , e dimostriamo che (yi+1)ⁿ > xi .

Se nell’iterazione i-esima al passo a) il valore di  è 0 (quindi se (2yi-1+1)ⁿ>2ⁿxi-1+i ) allora è ovvio perché appunto (yi+1)ⁿ=(2yi-1+1)ⁿ>2ⁿxi-1+i = xi .

Se invece il valore di  è 1, e se fosse per assurdo (yi+1)ⁿ  xi , si avrebbe:

(yi+1)ⁿ=(2yi-1+2)ⁿ=2ⁿ(yi-1+1)ⁿ xi=2ⁿxi-1+i da cui:

2ⁿ[(yi-1+1)ⁿ-xi-1]  i

ed essendo per l’ipotesi induttiva (yi-1+1)ⁿ-xi-1>0, si avrebbe 2ⁿ i , in contraddizione con quanto notato all’inizio.

In particolare per i=k si ottiene:

yknxk=x (yk+1)ⁿ > xk=x

Dunque l’output yk è effettivamente il più grande intero y tale che la yⁿx , quindi yk è la parte intera della radice n-esima dell’input x.

Resta da esaminare la complessità di calcolo dell’algoritmo.