Lezione del 18 marzo 2007 Aritmetica dei numeri naturali.
Nell’insieme N dei numeri naturali (ossia dei numeri interi >0) supporremo note le proprietà elementari delle operazioni aritmetiche (somma, differenza, prodotto) e dell’ordinamento.
Ricordiamo fra le proprietà dell’insieme N dei numeri naturali il cosiddetto Assioma del buon ordinamento (o del minimo): in un qualunque sottoinsieme S non vuoto di N esiste sempre un minimo sS (tale che s≤x per ogni xS).
E’ ovvio che la stessa proprietà vale anche per ogni sottoinsieme non vuoto S di N{0}, in quanto se S contiene 0, allora 0 è il minimo in S.
Principio di induzione (Ia forma):
Sia P(n) una proprietà relativa ad un generico numero naturale n (si dice anche che P(n) è un predicato nella variabile n, con n che assume valori in N).
Se:
1) P(1) è vero
2) P(n) vero P(n+1) vero allora P(n) è vero per ogni n in N.
Dimostrazione.
Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.
Allora s>1, per l’ipotesi 1), dunque s-1N, e poiché s-1<s, si ha s-1S, dunque P(s-1) è vero, ossia P(s) è vero, per l’ipotesi 2), contraddizione.
Il numero 1 è detto anche base dell’induzione.
Esistono altre versioni dello stesso principio in cui la base dell’induzione può essere un fissato numero naturale n0: in tale caso l’ipotesi 1) diventa “P(n0) è vero”, l’ipotesi 2) diventa “P(n) vero P(n+1) vero per ogni nn0”, la tesi diventa “P(n) è vero per ogni naturale nn0”.
Esiste anche una versione del principio di induzione riferita ad un predicato P(n) in cui la variabile n non assume tutti i valori naturali, ma solo i valori consecutivi da 1 a un naturale fissato n0, e in questo caso l’ipotesi 2) diventa “P(n) vero P(n+1) vero per ogni n=1,….,n0-1”, e la tesi diventa
“P(n) è vero per ogni n=1,2,….,n0” . Principio di induzione (IIa forma):
Sia P(n) una proprietà relativa ad un generico numero naturale n.
1) P(1) è vero
2) P(k) vero per tutti i k=1,2,…,n-1 P(n) vero allora P(n) è vero per ogni n in N.
Dimostrazione.
Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.
Allora s>1, per l’ipotesi 1), dunque 1,2,…s-1N, e poiché 1,2,…,s-1<s, si ha 1,2,…,s-1S. Dunque P(1), P(2), ……, P(s-1) sono veri, ossia P(s) è vero, per l’ipotesi 2), contraddizione.
Anche per questa forma del principio esistono altre versioni con base dell’induzione qualunque, o valide per un numero finito di valori di n.
Teorema dell’algoritmo della divisione per i numeri naturali.
Dati comunque i naturali a,b (a=dividendo, b=divisore), esistono e sono unici i numeri interi q,r0 (q=quoziente, r=resto) tali che a=bq+r, con r<b.
Dimostrazione.
Esistenza di q,r: Sia S={x0 / x=a-by, con y intero 0}. Poiché aS, tale S è sottoinsieme non vuoto di N{0}, e sia s il minimo in S. Si ha s0, s=a-by, con y intero 0, a=by+s. Se poniamo q=y, r=s, avremo la tesi se dimostreremo che s<b: se per assurdo fosse sb, si avrebbe s-b0, s-b=a- b(y+1)S, s-b<s, contraddizione.
Unicità di q,r: Dimostriamo prima l’unicità di r, supponendo per assurdo che sia a=bq+r=bq1+r1
con q,q1,r,r1 interi 0, r,r1<b, ed rr1 (per es. r>r1). Allora si avrebbe r-r1>0, r-r1r<b, r-r1=b(q1-q), quindi anche q1-q>0, cioè q1-q1, b(q1-q)b, contraddizione. Quindi è vero che r=r1. Da ciò si deduce anche 0=r-r1=b(q1-q), ossia q=q1 .
Dimostreremo ora che è possibile trovare quoziente e resto della divisione fra due numeri naturali, con un algoritmo di complessità polinomiale.
Se a=dividendo, b=divisore , possiamo assumere che sia ab (se a<b la divisione si effettua in modo banale con quoziente q=0, resto r=a).
Si ha allora certamente n=L(a)m=L(b).
La divisione di a per b si può effettuare con l’usuale algoritmo “scolastico”: il vantaggio di utilizzare cifre binarie 0,1 consiste nel fatto che la moltiplicazione di un numero per 1 dà come risultato il numero stesso, mentre per 0 dà come risultato 0.
Facciamo un esempio: siano a=(1101101)2, b=(101)2.
Prima “stacchiamo” (da sinistra) nel divisore a un “segmento” binario (di lunghezza minima) che non sia inferiore al divisore b (in questo caso è il segmento 110 di lunghezza 3) e sottraiamo da tale segmento il valore del divisore b, dando nello stesso tempo il valore 1 al primo bit del quoziente q:
1101101 101
101 1
1
In seguito “abbassiamo” il prossimo bit del dividendo, ma poiché otteniamo un numero 11 inferiore al divisore, diamo il valore 0 al secondo bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 111 non inferiore al dividendo: diamo allora il valore 1 al terzo bit del quoziente e sottraiamo dal numero 111 così ottenuto il valore del divisore: 1101101 101
101 101
111
101
10
Di nuovo “abbassiamo” il prossimo bit del dividendo, ma poiché otteniamo un numero 100 inferiore al divisore, diamo il valore 0 al quarto bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 1001 non inferiore al dividendo: diamo allora il valore 1 al quinto bit del quoziente e sottraiamo dal numero 1001 così ottenuto il valore del divisore: 1101101 101
101 10101
111
101
1001
101
100
Avendo ottenuto un valore 100 che è inferiore al divisore, l’algoritmo si ferma con output quoziente q=(10101)2 , e resto r=(100)2.
In generale se n=L(a)m=L(b), l’algoritmo esegue un numero di sottrazioni ≤n fra coppie di numeri di lunghezza ≤n , e poiché ognuna di tali sottrazioni ha (come visto nell’algoritmo Diff(x,y)) complessità lineare O(n), l’algoritmo della divisione ha complessità O(n2) quadratica, e dunque polinomiale.
L’algoritmo si può formalizzare nel modo seguente:
Sia n la dimensione di a, cioè il numero di cifre (binarie) di a:
a=an-12n-1+an-22n-2+…..+a121+a020 dove ogni ai=0,1, an-1=1 .
In output avremo le cifre binarie del quoziente q= qn-12n-1+qn-22n-2+…..+q121+q020 e il resto r<b (non è detto che il quoziente abbia esattamente dimensione n, perché alcune delle prime cifre qi
potranno essere =0).
L’algoritmo esegue i seguenti passi:
1) Si pone bn-1=1
2) Si esegue un ciclo di n-1 iterazioni, per i=1,….,n-1:
se bbn-i allora si pone qn-i=1, bn-i-1=2(bn-i-b)+an-i-1; in caso contrario si pone qn-i=0, bn-i-1=2bn-i+an-i-1
(tale ciclo definisce le cifre qn-1,….,q1, e costruisce i numeri bn-1,…,b0 ; notare che in ogni caso si ha bn-i-1=2(bn-i-bqn-i)+an-i-1 ad ogni iterazione)
3) Se bb0 allora si pone q0=1, r=bo-b; in caso contrario si pone q0=0, r=bo
(questo passo costruisce l’ultima cifra q0 del quoziente e il resto r; notare che in ogni caso si ha r=b0-bq0).
Posto q= qn-12n-1+qn-22n-2+…..+q121+q020 , dobbiamo verificare che 0r<b, e che a=bq+r.
Si verifica per induzione che per ogni i>0 si ha:
bn-i=(an-12i-1+an-22i-2+…+an-i+121+an-i20)-b(qn-12i-1+qn-22i-2+…+qn-i+121). (*) Infatti per i=1 si ha bn-1=1=an-1.
Supponendo vera la (*) per i, dimostriamola per i+1:
bn-(i+1)=bn-i-1=2(bn-i-bqn-i)+an-i-1=(an-12i+an-22i-1+…+an-i21+an-i-120)-b(qn-12i+qn-22i-1+…+qn-i21) In particolare per i=n si ha:
b0=(an-12n-1+an-22n-2+…..+a121+a020)-b(qn-12n-1+qn-22n-2+…+q121) da cui:
r=b0-bq0=(an-12n-1+an-22n-2+…..+a121+a020)-b(qn-12n-1+qn-22n-2+…+q121+q020)=a-bq . Inoltre si verifica per induzione che per ogni i>0 si ha:
0bn-i<2b . (**)
Infatti per i=1 si ha 0bn-1=1<2b (perché b>0).
Supponendo vera la (**) per i, dimostriamola per i+1:
seguendo l’algoritmo, se bbn-i allora si ha bn-i-1=2(bn-i-b)+an-i-10 (essendo (bn-i-b),an-i-10), e inoltre bn-i-1=2(bn-i-b)+an-i-12(2b-1-b)+an-i-1=2b+(an-i-1-2)<2b (essendo an-i-1=0,1) ;
se invece b>bn-i allora si ha bn-i-1=2bn-i+an-i-10 (essendo bn-i,an-i-10) e inoltre bn-i-1=2bn-i+an-i-1
2(b-1)+ an-i-1=2b+(an-i-1-2)<2b (come sopra).
La (**) in particolare per i=n fornisce:
0b0<2b
Da ciò possiamo dedurre che 0r<b: infatti nell’istruzione 3) vi sono 2 casi e in ambedue verificheremo la tesi:
- se bb0 allora si pone r=bo-b, dunque banalmente r0, ma anche r<b perché b0<2b - se b>b0 allora si pone r=b0 , dunque r<b ed inoltre r0 perché b00.
Divisori e massimo comune divisore.
Dati 2 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 è un numero naturale, essendo a,b>0).
Dati dunque 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à quadratica O(n2) (se n=L(a), con ab: ovviamente se a<b è certamente falso che bïa).
Dati 2 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 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 2 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, dove x,yZ}.
Tale insieme è non vuoto (almeno a=a1+b0S): sia d il minimo in S.
In particolare d=ax+by, dove 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, r<d, contraddizione.
Analogamente si verifica che dïb.
Se inoltre d0 è un 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 x,yZ . Tali coefficienti x,y non sono univocamente determinati: per esempio per ogni intero relativo k si ha ax+by=a(x+kb)+b(y-ka).
