Lezione del 20 marzo 2007

Lezione del 20 marzo 2007

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)+b1 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 dN, ed 1=mcd(a,b)=ax+by, con x,yZ, 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,yZ, 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,r0

si ha:

1) se r=0 (cioè 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 (q10, 0<r1<b) b=r1q2+r2 (q20, 0<r2<r1) r1=r2q3+r3 (q30, 0<r3<r2) .

.

rn-3=rn-2qn-1+rn-1 (qn-10, 0<rn-1<rn-2) rn-1=mcd(a,b) rn-2=rn-1qn+rn (qn0, 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 la complessità dell’algoritmo Euclideo: poiché ogni passo dell’algoritmo consiste in una divisione (di complessità quadratica O(k²) dove k è la lunghezza dell’input a, supponendo a>b, e notando che tutti i dividendi e divisori delle divisioni sono allora <a), è ovvio come 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, e per ogni n >2 Fn=Fn-1+Fn-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 cifre consecutive =1 consecutive è 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).

Supponiamo vera l’affermazione per ogni k<n e dimostriamola per n.

Consideriamo una generica parola w di lunghezza n che non contiene 2 cifre consecutive =1.

Distinguiamo 2 casi:

1) se l’ultima cifra di w è 0, la parola w si ottiene da una parola di lunghezza n-1 (che non contiene 2 cifre consecutive =1) aggiungendo come ultima cifra 0. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di Fn+1

2) se l’ultima cifra è 1, la parola w si ottiene da una parola di lunghezza n-2 (che non contiene 2 cifre consecutive =1) aggiungendo come penultima cifra 0 e come ultima cifra 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 x²+ax-a² = 0, da cui x = a(-1 ⁵)/2

Essendo x>0, l’unico valore accettabile è x = a(-1+ 5)/2, da cui a/x = 2/(-1+ 5)=( 5

+1)/21,61 (è il cosiddetto rapporto aureo o numero d’oro).

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 circonscritta.