Quozienti, resti, numeri primi. Lezione del 28.3.07 1. La divisione

Quozienti, resti, numeri primi.
Lezione del 28.3.07
1. La divisione nell'insieme dei numeri naturali.
Dati i naturali a e b 6= 0, detti, rispettivamente, dividendo e divisore, si
dimostra che esistono un unico naturale q , detto quoziente, ed un unico
naturale r, detto resto, tali che
a = b × q + r con 0 ≤ r < b.
La divisione, intesa in questo senso, associa alla coppia (a, b) la coppia (q, r).
Esempi: i) se a = 25, b = 7, allora q = 3 e r = 4;
ii) se a = 14, b = 20, allora q = 0 e r = 14;
iii) se a = 120, b = 6, allora q = 20 e r = 0.
Nel caso in cui risulti r = 0, si dice che a e' multiplo di b, oppure che
b divide a.
2. Relazioni di equivalenza.
In un insieme A, supponiamo di aver denito un criterio che permetta
di dividere le coppie di elementi di A in due categorie: le coppie che
vericano il criterio e le coppie che non lo vericano. Chiamando R il
criterio, scriveremo aRb per indicare che la coppia (a, b)verica il criterio,
dove a e b sono elementi di A.
Per esempio, se A e' un insieme di oggetti, possiamo introdurre il criterio
avere lo stesso peso e scrivere aRb se gli oggetti a e b hanno lo stesso peso;
oppure, se A e' l'insieme delle rette del piano, possiamo scrivere aRb
per denotare che a e b sono perpendicolari.
Il criterio viene chiamato relazione e una relazione in A si dice relazione di
equivalenza se verica le seguenti tre proprieta':
1) riessivita': aRa per ogni a di A,
2) simmetria: se aRb, allora bRa,
3) transitivita': se aRb e bRc, allora aRc.
Il criterio avere lo stesso peso e' una relazione di equivalenza, mentre
essere perpendicolari non lo e', in quanto non e' ne' riessivo ne' transitivo.
Se R e' una relazione di equivalenza in A, si chiama classe di equivalenza
di a in A
[a] = {b ∈ A : aRb}
e si dimostra che le classi di equivalenza costituiscono una partizione dell'
insieme A, vale a dire la loro unione e' l'insieme A e due classi di equivalenza
diverse sono necessariamente disgiunte.
3. La congruenza nei numeri naturali.
Fissato il numero naturale n 6= 0, due naturali a e b si dicono congrui
modulo n e si scrive
1
a ≡ b mod n
se a e b hanno lo stesso resto nella divisione per n.
Si verica che la congruenza mod n e' una relazione di equivalenza in N.
Per esempio, se n = 3, dato che i resti possibili nella divisione per 3 sono
0, 1, 2, abbiamo tre classi di equivalenza, denotate con
[0] = {0, 3, 6, 9, ....}
[1] = {1, 4, 7, 10, ...}
[2] = {2, 5, 8, 11, ...}.
La loro unione e' N e sono a due a due disgiunte.
La divisione e la relazione di congruenza si possono estendere all'insieme
Z dei numeri interi (Z = {..., −3, −2, −1, 0, 1, 2, 3, ...}).
4. I numeri primi
Un numero naturale p 6= 1 si dice primo se i suoi unici divisori sono 1
e p.
Sono validi i seguenti due risultati:
1) ogni numero naturale maggiore o uguale a 2 e' divisibile per un
numero primo;
2) se il numero primo p divide il prodotto a × b, allora p divide a
oppure p divide b.
La proprieta' 2) non e' vericata dai numeri che non sono primi:
ad esempio, se p = 15, p divide 5 × 3, ma p non divide ne' 5 ne' 3.
I numeri primi sono inniti.
Vale il teorema fondamentale dell'aritmetica:
Ogni numero naturale maggiore o uguale a 2 si scompone, in maniera
unica, in un prodotto di potenze di numeri primi.
Per esempio
250 = 2 × 53 , ma 250 = 25 × 10 = 5 × 50.
5. Massimo comune divisore e minimo comune multiplo.
Dati a e b due naturali non tutti e due nulli, si denisce massimo comune
divisore di a e b , e si denota con mcd(a, b), un naturale k che divida sia
a che b e tale che, se c divide anch'esso a e b, allora c divide k .
Si dimostra che esiste un unico massimo comune divisore che puo'
essere ottenuto come il prodotto dei numeri primi comuni alle
scomposizioni di a e b elevati all'esponente piu' piccolo che compare
nelle due scomposizioni.
Un'altra maniera con la quale si puo' calcolare il massimo comune
divisore e' data dall'algoritmo di Euclide.
Vediamolo su un esempio:
si debba calcolare il massimo comune divisore di 7624 e di 198:
cominciamo col dividere 7624 per 198:
7624 = 38 × 198 + 100;
dividiamo 198 per 100:
2
198 = 1 × 100 + 98;
dividiamo 100 per 98:
100 = 1 × 98 + 2;
dividiamo 98 per 2:
98 = 2 × 49 + 0.
Il massimo comune divisore e' l'ultimo resto diverso da zero; in questo
caso otteniamo 2.
Si chiama minimo comune multiplo di a e b, e si denota con mcm(a, b),
un numero m che sia multiplo di a e di b e tale che , se c e' multiplo sia
di a che di b, allora c e' multiplo di m.
Anche qui si dimostra che esiste un unico minimo comune multiplo che puo'
essere ottenuto come il prodotto di tutti i primi che compaiono nelle
scomposizioni di a e b, elevati all'esponente piu' grande che compare nelle
scomposizioni stesse.
Vale la formula
a × b = mcd(a, b) × mcm(a, b).
6. Interi primi fra loro.
Due interi si dicono primi fra loro se hanno massimo comune divisore
uguale a 1.
Questo equivale a dire che i due numeri non hanno numeri primi in
comune nelle loro scomposizioni.
Per esempio, 6 e 35 sono primi fra loro (e non sono primi).
Due interi a e b sono primi fra loro se e solo se esistono due interi s e t tali
che
a × s + b × t = 1.
Dati comunque due interi a e b, risultano sempre primi fra loro gli interi
a
b
a0 = mcd(a,b)
e b0 = mcd(a,b)
.
3