Teoria dei numeri e Crittografia: lezione del 31 marzo 2011 Divisori e massimo comune divisore.
Dati i numeri naturali a,b diremo che b è divisore di a (equivalentemente che a è multiplo di b) e scriveremo il simbolo bïa, se esiste un numero intero relativo c tale che a=bc (notare che c è necessariamente un numero naturale, essendo a,b>0; inoltre da c1 segue necessariamente ab).
Dati a,bN , per testare se bïa basta effettuare la divisione di a per b, calcolare quoziente q e resto r, e verificare se r=0: si ha infatti bïa r=0 ( è ovvia; deriva dall’osservazione che se a=bc=bc+0=bq+r, si ha r=0, per l’unicità del resto).
Quindi il test di divisibilità per i numeri naturali si può effettuare con un algoritmo (quello della divisione) di complessità ≤O(x2) (se x=L(a), con ab: ovviamente se a<b è certamente falso che bïa).
Dati i numeri naturali a,b chiameremo massimo comune divisore di a,b un numero naturale d tale che dïa, dïb (cioè d è divisore comune di a,b) e inoltre d è multiplo di tutti i numeri naturali divisori comuni di a,b.
La seconda proprietà garantisce che d è il più grande dei numeri naturali divisori comuni di a,b ed in particolare è unico (se esiste): scriveremo allora d=mcd(a,b).
Teorema dell’esistenza del mcd(a,b):
Comunque dati i numeri naturali a,b esiste d=mcd(a,b).
Dimostrazione.
Consideriamo l’insieme di tutti i numeri naturali che sono “combinazioni lineari” di a,b a coefficienti interi relativi: S={c / c>0, c=ax+by, x,yZ}.
Tale insieme è non vuoto (almeno a=a1+b0S): sia d il minimo in S.
In particolare d=ax+by, per opportuni x,yZ.
Verifichiamo che d =mcd(a,b).
Per verificare se dïa dividiamo a per d, ottenendo quoziente q e resto r tali che a=dq+r, con r<d, e dimostriamo che r=0. Se per assurdo fosse r>0, sarebbe r=a-dq=a(1-xq)+b(-yq)S, contraddizione (perché r<d e d è il minimo in S).
Analogamente si verifica che dïb.
Se inoltre d0 è un numero naturale divisore comune di a,b allora esistono numeri naturali s,t tali che d0s=a, d0t=b, da cui d=ax+by=d0(sx+ty) cioé d0 è divisore di d.
Nota: nella dimostrazione precedente si è anche notato che d=mcd(a,b) è una combinazione lineare della forma d=ax+by, per opportuni coefficienti interi relativi x,yZ . Tali coefficienti x,y non sono però univocamente determinati: per esempio per ogni intero relativo k si ha:
ax+by=a(x+kb)+b(y-ka).
Due numeri naturali a,b sono detti coprimi o relativamente primi se mcd(a,b)=1, o equivalentemente se 1 è l’unico loro divisore comune.
Proprietà elementari:
1) Se 1=ax+by è combinazione lineare di a,b con coefficienti interi relativi x,y, allora a,b sono coprimi.
Basta infatti ricordare che il mcd(a,b) è la minima delle combinazioni lineari >0 di a,b, quindi certamente 1=mcd(a,b).
2) Due numeri naturali consecutivi a, b=a+1 sono sempre coprimi.
Basta osservare che 1=a(-1)+b1 e applicare la 1).
3) Dividendo due numeri naturali a,b per il loro massimo comune divisore d=mcd(a,b) si ottengono due numeri naturali coprimi.
Infatti posto d=ax+by (con x,y interi relativi), si ha 1=(a/d)x+(b/d)y, e applicando la 1) si ottiene che a/d, b/d sono coprimi.
4) Dati 3 numeri naturali a,b,c, se aï(bc) e se a,b sono coprimi allora aïc.
Infatti, posto bc=ad, con dN, ed 1=mcd(a,b)=ax+by, con x,yZ, si ha c=acx+bcy=a(cx+dy).
5) Dati 3 numeri naturali a,b,c, se aïc, bïc, e se a,b sono coprimi allora (ab)ïc .
Infatti, posto c=ar=bs, con r,s N, ed 1=mcd(a,b)=ax+by, con x,yZ, si ha c=acx+bcy=ab(sx+ry).
Lemma:
Dati 2 numeri naturali a,b ed effettuata la divisione con a=dividendo, b=divisore : a=bq+r q,r0 r<b
si ha:
1) se r=0 (equivalentemente se bïa) allora mcd(a,b)=b 2) se r>0 allora mcd(a,b)=mcd(b,r)
Dimostrazione.
La dimostrazione di 1),2) segue facilmente dalla definizione di massimo comune divisore.
Illustriamo un algoritmo per calcolare d=mcd(a,b), dati i numeri naturali a,b: è il cosiddetto algoritmo Euclideo delle divisioni successive.
Esso consiste nei seguenti passi:
1) Si divide a per b trovando quoziente e resto
2) Si effettuano successive divisioni con il seguente criterio: ogni volta che una divisione ha resto non nullo, si effettua una successiva divisione prendendo come dividendo e divisore rispettivamente divisore e resto della precedente divisione. L’algoritmo si ferma quando si ottiene una divisione con resto nullo
3) Il resto (non nullo) della penultima divisione è il mcd(a,b).
Schematizzando l’algoritmo:
a=bq1+r1 (q10, 0<r1<b) b=r1q2+r2 (q20, 0<r2<r1) r1=r2q3+r3 (q30, 0<r3<r2) .
.
rn-3=rn-2qn-1+rn-1 (qn-10, 0<rn-1<rn-2) rn-2=rn-1qn+rn (qn0, rn=0)
Output: rn-1=mcd(a,b)
Prima di tutto osserviamo che l’algoritmo si ferma dopo un numero finito di divisioni : infatti la successione dei resti è decrescente, e se per assurdo si ottenessero sempre resti >0, il loro insieme sarebbe un sottoinsieme di N senza minimo, contro l’assioma del minimo.
Inoltre l’affermazione che rn-1=mcd(a,b) si può dimostrare applicando più volte il precedente Lemma:
mcd(a,b)=mcd(b,r1)=mcd(r1,r2)=….=mcd(rn-2,rn-1)=rn-1 .
Calcoleremo ora la complessità dell’algoritmo Euclideo: poiché ogni passo dell’algoritmo consiste in una divisione è ovvio che sia necessario dare una stima (nel caso peggiore) del numero n delle divisioni effettuate nell’algoritmo. A tale scopo ricordiamo la teoria dei numeri di Fibonacci.
La successione di Fibonacci.
La successione dei numeri di Fibonacci è la successione di numeri naturali Fn (n>0) definita ponendo: F1=F2=1, Fn=Fn-1+Fn-2 per ogni n >2
Quindi F3=2; F4=3, F5=5, F6=8 etc…
Tale successione interviene in molti problemi combinatori.
Esempio. Per ogni naturale n, il numero delle parole di lunghezza n sull’alfabeto {0,1} che non contengono 2 bits =1 consecutivi è Fn+2.
Per dimostrarlo basta usare la seconda forma del principio di induzione.
Per n=1 l’affermazione è banale: sono 2=F3 le parole in questione (le parole 0 e 1).
Sia n>1: supponiamo vera l’affermazione per ogni numero naturale k<n e dimostriamola per n.
Consideriamo una generica parola w di lunghezza n che non contiene 2 bits consecutivi =1.
Distinguiamo 2 casi:
1) se l’ultimo bit di w è 0, la parola w si ottiene da una parola di lunghezza n-1 (che non contiene 2 bits consecutivi =1) aggiungendo come ultimo bit 0. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di Fn+1
2) se l’ultimo bit è 1, la parola w si ottiene da una parola di lunghezza n-2 (che non contiene 2 bits consecutivi =1) aggiungendo come penultimo bit 0 e come ultimo bit 1. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di Fn
In totale il numero di valori di w è Fn+Fn+1=Fn+2 .
Problema: trovare una formula algebrica per il calcolo del generico numero di Fibonacci Fn . A tale scopo ricordiamo alcune classiche nozioni geometriche.
Se AB è un segmento di estremi A,B è di lunghezza a (con a reale >0), si chiama parte aurea di AB un segmento AC (dove C è un punto interno ad AB) tale che la lunghezza x di AC sia media proporzionale fra a e la lunghezza (a-x) del segmento CB:
a : x = x : (a-x)
e da ciò si ricava x2+ax-a2 = 0, da cui x = a(-1 5)/2.
Essendo x>0, l’unico valore accettabile è x = a(-1+ 5)/2, da cui si ottiene il valore del rapporto:
a/x = 2/(-1+ 5)=( 5+1)/21,61
(è il cosiddetto rapporto aureo o numero d’oro, indicato spesso con la lettera greca ).
Il concetto di parte aurea di un segmento ha molte applicazioni geometriche: per esempio il lato del decagono regolare ha la stessa lunghezza della parte aurea del raggio della circonferenza circoscritta.
Descriviamo alcune proprietà del numero d’oro :
1) Nel ragionamento precedente, poiché x è soluzione di x2+ax-a2 = 0, dividendo per x2 si ottiene che = a/x soddisfa l’identità:
1 + - 2 = 0 da cui:
2 = 1+ (*) 2) Si ricava anche:
(1-)2 = 1-2+2
e tenendo conto di (*) si ottiene:
(1-)2 = 2- (**)
Il numero d’oro ha una stretta relazione con la successione dei numeri di Fibonacci Fn .
Calcolando le potenze di base ad esponente naturale e confrontandole con alcuni valori di Fn, osserviamo che:
F2=1 < 11,61 < F3=2 < 22,6 < F4=3 < 34,2 < F5=5 e si può congetturare che si abbia :
Fn+1 < n < Fn +2 (***) per ogni naturale n.
Possiamo dimostrare che ciò è vero, ragionando per induzione (IIa forma). Per n=1 abbiamo già notato che (***) è vero.
Sia n>1: supponiamolo vero per tutti i k<n, e dimostriamolo vero per n; poiché (***) è in particolare vero per k=(n-1),(n-2), si ha Fn < n -1< Fn +1 , Fn-1 < n -2< Fn , da cui, sommando, si ha:
Fn+1 = Fn+Fn-1 < n –1 + n –2 < Fn+1+Fn = Fn+2
Ma dalla (**) segue che:
n –1 + n –2 = n –2(1+) = n quindi la (***) é vera per n.
Dimostriamo ora la seguente formula algebrica per il calcolo del generico numero di Fibonacci:
Fn = [n – (1-)n]/ 5 per ogni naturale n.
Ragioniamo di nuovo per induzione (IIa forma). Per n=1 si ha:
[ – (1-)]/ 5= (2-1) / 5= 1 = F1
Sia n>1: supponiamo la formula vera per ogni k<n e dimostriamola per n; poiché è vera in particolare per k=(n-1),(n-2), si ha:
Fn-1 = [n-1 – (1-)n-1]/ 5 , Fn-2 = [n-2 – (1-)n-2]/ 5 e sommando si ottiene (tenendo conto di (*) e (**)):
Fn-1 + Fn-2 = Fn = [n-2(1+) - (1-)n-2(2-)]/ 5= [n – (1-)n]/ 5 come si voleva.
In effetti la formula ottenuta per il calcolo dei numeri di Fibonacci è poco utile, perché coinvolge numeri irrazionali.
