Matematica Discreta
Lezione del giorno 29 novembre 2011 Divisori e multipli fra i numeri naturali
Dati 2 numeri naturali a,b diremo che b è divisore di a (o che a è multiplo di b o ancora che b divide a) se esiste un numero naturale c tale che a=bc: in tale caso scriveremo il simbolo ba. Per esempio 28 perché esiste il numero naturale c=4 tale che 8=24.
Algoritmo della divisione fra i numeri naturali.
E’ ben noto che, dati 2 numeri interi positivi, si possa “dividere” il primo (dividendo) per il secondo (divisore) trovando un “quoziente” e un “resto”.
Dimostreremo formalmente tale proprietà:
Teorema dell’algoritmo della divisione.
Comunque dati 2 numeri naturali a,b (detti rispettivamente “dividendo” e “divisore”), esistono due numeri interi q,r0 (detti rispettivamente ”quoziente” e “resto”) tali che a=bq+r con r<b.
Inoltre il quoziente q e il resto r sono unici.
Dimostrazione:
Dimostrazione dell’esistenza di q,r: si consideri l’insieme di tutte le differenze della forma a-bx, con x che varia fra gli interi 0, limitandosi a quelle differenze che danno un risultato 0:
S = { z / z=a-bx, con x intero 0, e con z 0 }
L’insieme S è non vuoto: infatti almeno la differenza a-b0=a è elemento di S, perché a>0.
Possiamo osservare che S contiene certamente un elemento minimo: infatti se S non contiene lo 0 allora S è sottoinsieme di N ed S contiene un elemento minimo per l’Assioma del minimo; se invece S contiene lo 0, è ovvio che 0 è il suo minimo. Sia dunque s il minimo in S. Per costruzione di S si ha che s è un intero 0, ed inoltre s=a-bx con x intero 0. Da cui a=bx+s, e basta scegliere r=s e q=x per avere l’esistenza di q ed r. Resta però da verificare che r<b: se per assurdo fosse rb, si avrebbe r-b0, r-b=(a-bq)-b=a-b(q+1), con q+10 (perché q=x0) dunque il numero r-b sarebbe una delle differenze che appartengono ad S; ma si avrebbe anche r-b<r (perché b>0), contraddizione perché r è il minimo in S.
Dimostrazione dell’unicità di q,r: se a=bq+r=bq1+r1 (con q,r,q1,r1 interi 0 e con r<b, r1<b) le tesi sono che r=r1, q=q1 .
Tesi r=r1 : se per assurdo fosse rr1, e se per esempio fosse r>r1 (se è al contrario r<r1 si ragiona in modo simile) si avrebbe r-r1>0, r-r1=b(q1-q), dunque q1-q>0, ossia q1-q1, r-r1=b(q1-q)b; ma si ha anche rr-r1=b(q1-q)b , contraddizione perché r<b.
Tesi q=q1 : avendo già dimostrato la prima tesi, si ha bq=a-r=a-r1=bq1, dunque q=q1 .
Il prossimo Teorema fornisce un criterio per stabilire quando un numero naturale b è divisore di un numero naturale a.
Teorema. Siano dati 2 numeri naturali a,b. Allora si ha:
ba dividendo a per b (con l’algoritmo della divisione) si ottiene resto 0 Dimostrazione:
Dimostriamo la doppia implicazione:
: Per ipotesi esiste un numero naturale c tale che a=bc. Dividiamo a per b ottenendo 2 numeri interi q,r≥0 (quoziente e resto) tali che a=bq+r, con r<b; ma si ha anche:
a=bq+r=bc+0 con 0<b
e per l’unicità del resto nella divisione di a per b si ottiene r=0 (tesi).
: Per ipotesi se dividiamo a per b otteniamo resto 0, quindi a=bq+r con r=0, ossia a=bq, con q (quoziente) numero intero0; ma si può notare che q è certamente positivo (perché a,b lo sono) quindi a=bq con q numero naturale e si ottiene la tesi ba.
Rappresentazione di un numero naturale in una generica base b>1.
È un’applicazione del teorema dell’algoritmo della divisione per i numeri interi.
Fissiamo un numero naturale a ed un naturale b>1 (detto “base”). Applicando l’algoritmo della divisione, operiamo una divisione, con a come dividendo e b come divisore, ottenendo l’esistenza di due interi q0 ed r0, entrambi ≥0, tali che a=bq0+r0, con r0<b. Se il quoziente q00 (cioè q0>0) operiamo un’altra divisione, prendendo q0 come dividendo e b come divisore e ottenendo l’esistenza di due interi q1 ed r1, entrambi ≥0, tali che q0=bq1+r1, con r1<b. Ancora, se il quoziente q10 (cioè q1>0), operiamo una terza divisione, prendendo q1 come dividendo e b come divisore, ottenendo l’esistenza di due interi q2 edr2, entrambi ≥0 tali che q1=bq2+r2, con r2>b; se q20 (q2>0) si ripete ancora il procedimento. In pratica tale procedimento continua con una successiva divisione solo se il quoziente della precedente divisione è non nullo: nella successiva divisione il dividendo coincide con il quoziente della divisione precedente, mentre il divisore rimane costantemente =b.
Il procedimento si arresta quando si perviene ad una divisione con quoziente nullo.
Dimostriamo che questo procedimento ha termine dopo un numero finito di divisioni.
Per assurdo supponiamo di operare infinite divisioni tutte con quoziente non nullo. Osserviamo che il quoziente di ogni divisione è minore del quoziente della divisione precedente: infatti, essendo b>1, si ha bq1>q1, ed essendo r1≥0, si ha q0=bq1+r1≥ bq1>q1, quindiq0>q1. Analogamente si dimostra che q2>q1, che q3>q2 etc.
Potremmo allora costruire l’insieme S che contiene tutti i quozienti q1, q2,….. delle divisioni effettuate: essendo per assurdo tali quozienti tutti non nulli, sarebbe un insieme di numeri interi >0, cioè di numeri naturali, e quindi, per l’Assioma del minimo, S conterrebbe un elemento minimo, diciamo qi .Ma, come osservato sopra, si avrebbe qi>qi+1 , contraddizione perché in S esisterebbe un elemento qi+1 minore del minimo qi .
Possiamo quindi affermare con certezza che dopo un numero finito di divisioni, perverremo ad una divisione con quoziente qn=0.
Elenchiamo le divisioni effettuate (supponendo appunto che il quoziente qn di indice n sia nullo):
a=bq0+r0
q0=bq1+r1
q1=bq2+r2
q2=bq3+r3
…….
…….
…….
qn-2=bqn-1+rn-1
qn-1=bqn+rn (con qn=0, quindi con qn-1=rn ).
Operando delle sostituzioni successive si ottiene:
a=bq0+r0=b(bq1+r1)+r0=b2q1+br1+r0=b2(bq2+r2)+br1+r0=b3q2+b2r2+br1+r0=………=
=bnqn-1+bn-1rn-1+…..+ b2r2+br1+r0=bnrn+ bn-1rn-1+…..+ b2r2+br1+r0 .
La scrittura ottenuta:
a=rnbn+rn-1bn-1+…..+r2b2+r1b+r0
è detta rappresentazione di a in base b ed i numeri r0,r1,r2,…rn sono detti cifre della rappresentazione. Come si nota nel procedimento precedente, le cifre r0,r1,r2,…rn (essendo resti delle
divisioni per b) sono numeri interi ≥0 e <b, cioè i possibili valori delle cifre sono compresi fra i numeri interi 0,1,…,b-1 , dove b è la base fissata.
Il simbolo usato per la rappresentazione di a in base b é è a=(rnrn-1rn-2……r2r1r0)b . Esempio:
Scrivere il numero a=122 in base b=3.
I valori possibili delle cifre nella rappresentazione in base 3 sono 0,1,2. Procedendo con l’algoritmo precedente otteniamo:
1a divisione: 122=340+2 dove 121=a, 3=b, 40= q0, 2=r0; 2a divisione: 40=313+1 dove 40=q0, 3=b, 13=q1, 1=r1; 3a divisione: 13=34+1 dove 13=q1, 3=b, 4=q2, 1=r2; 4a divisione: 4=31+1 dove 4=q2, 3=b, 1=q3, 1=r3; 5a divisione: 1=30+1 dove 1=q3, 3=b, 0=q4, 1=r4. Allora a=122=(11112)3 .
Il procedimento inverso si effettua opernado le moltiplicazioni delle singole cifre per le potenze della base (relative alla posizione della base stessa) e sommando i prodotti.
Esempio:
Calcoliamo l’usuale rappresentazione decimale (cioè in base 10) del seguente numero rappresentato in base 5: a=(10241)5.
(10241)5=154+053+252+451+150=625+0+50+20+1=696.
Particolari basi sono la base b=10 (decimale), che è quella usata comunemente (forse in relazione al numero di dita delle mani) e la base b=2 (binaria), le cui cifre sono 0 ed 1 e che si utilizza nei computers in quanto si può trovare una corrispondenza con gli stati dei circuiti elettronici (per es.
alta o bassa tensione).
Un’altra base spesso usata in Informatica è b=16: in questo caso il valore numerico delle cifre è compreso fra 0 e 15 (per le cifre di valore 10,11,12,13,14,15 si usano le lettere dell’alfabeto A,B,C,D,E,F).
