Matematica Discreta II
Lezione del giorno 17 ottobre 2007
Dato il monoide Zm={[0], [1], …., [m-1]} delle classi di congruenza modulo m rispetto al prodotto di classi, sappiamo che gli elementi simmetrizzabili formano un gruppo Zm* rispetto alla stessa operazione. Per quanto già dimostrato si ha:
Zm* = {[x] Zm / x=1,2,….,m-1; x,m coprimi}
Identificando [x] con il rappresentante numerico x, si può anche identificare Zm* con l’insieme dei numeri naturali x tali che 1xn-1, e tali che x,m siano coprimi: con tale identificazione il prodotto di due elementi x,y in Zm* è definito dalla riduzione modulo m del prodotto aritmetico xy, mentre il simmetrico di un elemento x in Zm* è definito dalla riduzione modulo m del coefficiente di x nella scrittura di 1 come combinazione lineare di x,m (calcolata con l’algoritmo Euclideo).
Ricordiamo i dettagli dell’algoritmo Euclideo delle divisioni successive.
Siano dati i numeri naturali a,b (con a>b): si effettua una prima divisione di a (dividendo) per b (divisore) ottenendo quoziente q1 e resto r1, dove q1, r1 sono interi 0, con r1<b; si effettuano poi successive divisioni con la regola seguente: effettuata la divisione numero k, se il resto è 0 l’algoritmo si arresta, mentre se il resto è >0 si effettua un’ulteriore divisione numero k+1, in cui il dividendo e il divisore sono rispettivamente il divisore e il resto della divisione numero k; l’ultimo resto non nullo è il mcd(a,b).
Schematizzando:
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-1=mcd(a,b) rn-2=rn-1qn+rn (qn0, rn=0)
Parallelamente si possono calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by:
si costruiscono le 2 seguenti successioni di numeri interi relativi s0 ,s1,…..,sn ; t0,t1,….,tn
ponendo
s0=1, s1=0, si=si-2-si-1qi-1 (per ogni i>1);
t0=0, t1=0, ti=ti-2-ti-1qi-1 (per ogni i>1)
dove qi-1 è il quoziente della divisione numero (i-1) nell’algoritmo Euclideo.
e basta poi porre x=sn ,y=tn per avere i coefficienti x, y.
Esempio.
Se a=89, b=33, nell’algoritmo Euclideo si effettuano n=5 divisioni con i seguenti valori di quoziente e resto:
q1=2, r2=23; q2=1, r2=10; q3=2, r3=3; q4=3, r4=1; q5=3, r5=0 concludendo che mcd(89,33)=r4=1.
Calcolando le successioni si, ti si ottiene s5=x=-10, t5=y=27, 1=89x+33y.
In particolare si ottiene che [33] è simmetrizzabile in Z89 con simmetrico [27].
Per capire la complessità di calcolo dell’algoritmo Euclideo (e quindi anche dell’algoritmo per il calcolo del simmetrico di un elemento simmetrizzabile di Zm) cercheremo di maggiorare il numero di divisioni che si effettuano nell’algoritmo stesso.
Prima introduciamo il principio di induzione, che si presenta in 2 forme:
Ia forma del principio di induzione: se P(n) è un predicato nella variabile n (numero naturale) e se a) P(1) è vero
b) per ogni naturale k, P(k) vero P(k+1) vero allora P(n) è vero per ogni naturale n.
(forma già dimostrata nel corso di Matematica Discreta I)
IIa forma del principio di induzione: se P(n) è un predicato nella variabile n (numero naturale) e se
a) P(1) è vero
b) per ogni naturale k>1, P(1), P(2), …., P(k-1) veri P(k) vero allora P(n) è vero per ogni naturale n.
Dimostrazione:
Per assurdo sia non vuoto l’insieme S dei naturali x tali che P(x) è falso e sia s il minimo in S (quindi P(s) è falso). Si ha s>1 (per l’ipotesi a)), ed essendo 1,2,…,s-1S, P(1),P(2),…,P(s-1) sono veri, dunque P(s) è vero (per l’ipotesi b)), contraddizione
La successione Fn (con n0) dei numeri di Fibonacci è definita ponendo:
F0=F1=1, Fn=Fn-1+Fn-2 (per ogni n>1).
Quindi F2=2; F3=3, F4=5, F5=8 etc…
Tale successione interviene in molti problemi combinatori.
Ricordiamo anche alcuni concetti geometrici: se AB è un segmento di estremi A,B è di lunghezza a (con a reale >0), si chiama parte aurea di AB un segmento AO (dove O è 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)
da cui si ricava x2+ax-a2 = 0, x = a(-1 5)/2
Essendo x>0, l’unico valore accettabile è x = a(-1+ 5)/2, da cui a/x = 2/(-1+ 5)=( 5
+1)/21,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.
Se indica il numero d’oro, possiamo notare che , essendo 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+ (*)
Il numero d’oro ha una 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:
F1=1 < 11,61 < F2=2 < 22,6 < F3=3 < 34,2 < F4=5 e si può congetturare che si abbia :
Fn < n < Fn +1 (**) per ogni naturale n.
Possiamo dimostrare che ciò è vero, ragionando per induzione (IIa forma). Per n=1 abbiamo già notato che (**) è vero.
Supponiamolo vero per n=1,….,k-1, e dimostriamolo vero per n=k; poiché (**) è per ipotesi vero in particolare per n=k-1, n=(k-2), si ha Fk-1 < k-1< Fk , Fk-2 < k-2< Fk-1 , da cui, sommando, si ha:
Fk = Fk-1+Fk-2 < k–1 + k–2 < Fk+Fk-1 = Fk+1
Ma dalla (*) segue che:
k–1 + k–2 = k–2(1+) = k quindi la (**) é vera per n=k.
Siano a,b numeri naturali, con a>b. Effettuiamo le n divisioni successive dell’algoritmo Euclideo:
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-1=mcd(a,b) rn-2=rn-1qn+rn (qn0, rn=0)
Per costruzione si ha :
a > b > r1 > r2 > …….. > rn-1 > 0=rn
dunque in particolare i quozienti qi sono tutti non nulli.
Poniamo per omogeneità r0=b (in modo che la prima divisione sia a=r0q1+r1) e dimostriamo che si ha:
rn-j Fj+1 per ogni j naturale Ragioniamo per induzione (IIa forma).
Per j=1 si ha (essendo rn-1>0) : rn-1 F2 = 1.
Fissato k>1, supponiamolo vero per tutti i j=1,2,…,k-1 e dimostriamolo vero per j=k.
Essendo vero in particolare per j=k-1, j=k-2, si ha:
rn-k+1 Fk , rn-k+2 Fk-1
Ricavando il resto rn-k dalla divisione numero n-k+2 si ha (tenendo conto che qn-k+21):
rn-k = rn-k+1qn-k+2+rn-k+2 rn-k+1+rn-k+2 Fk + Fk-1 = Fk+1
come si voleva.
In particolare, per j=n, si ha b = r0 Fn+1 , ma n-1 < Fn+1 (per la proprietà già dimostrata che lega i numeri di Fibonacci alle potenze del numero d’oro ), dunque n-1 < b, ossia (estraendo il logaritmo in base 10):
(n-1)log10 < log10b
Poiché log100,206>1/5 si ottiene (n-1) < (log10b)/5
Se t è il numero di cifre nella rappresentazione di b in base 10 si ha : 10t-1 b< 10t
e dunque log10b < t, da cui n 5t.
In pratica quindi il numero di divisioni nell’algoritmo Euclideo non è superiore al quintuplo del numero di cifre del più piccolo dei numeri a,b (rappresentati in base 10).
Per esempio se a=F11=144, b=F10=89, si effettuano n=10 divisioni (per concludere che 1=mcd(a.b)), quindi il numero di divisioni in questo caso coincide esattamente con il quintuplo del numero di cifre del più piccolo dei numeri a,b (rappresentati in base 10).
