Next: Lezione 10
Up: Matematica Discreta (II modulo)
Previous: Lezione 8
Subsections
Definizione 9.1
Dati due interi
![$ n,m$](img743.gif)
si dice che
![$ n$](img2.gif)
è un
divisore di
![$ m$](img218.gif)
(o che
![$ m$](img218.gif)
è un
multiplo di
![$ n$](img2.gif)
) se esiste un
![$ k\in\mathbb{Z}$](img744.gif)
tale
che
![$ m=nk$](img745.gif)
. Si indica con
![$ n\mathrel{\big\vert}m$](img746.gif)
(si legge
divide
![$ m$](img218.gif)
).
Esempio 9.2
![$ n\mathrel{\big\vert}0$](img747.gif)
per ogni
![$ n$](img2.gif)
mentre se
![$ n\ne 0$](img215.gif)
allora
![$ 0\not\mathrel{\big\vert}n$](img748.gif)
, si ha
inoltre che
![$ \pm1\mathrel{\big\vert}n$](img749.gif)
e
![$ \pm n\mathrel{\big\vert}n$](img750.gif)
per ogni
![$ n$](img2.gif)
.
Dimostrazione.
1. Se
e
allora
ossia
.
2. Se
e
allora
e quindi
e quindi o
e quindi anche
, oppure
ma
allora o
e quindi
oppure
e quindi
.
Definizione 9.4
Il numero
![$ n$](img2.gif)
si dice
primo se i suoi unici divisori sono
![$ \pm1,\pm n$](img767.gif)
.
Proposizione 9.6
Se
![$ d$](img768.gif)
e
![$ d'$](img774.gif)
sono due massimi comun divisori tra
![$ n$](img2.gif)
e
![$ m$](img218.gif)
allora
![$ d'=\pm d$](img775.gif)
.
Dimostrazione.
è un divisore comune di
e
, quindi poiché
è un massimo comun divisore si ha che
. Scambiando i
ruoli di
e
si ha allora che anche
e quindi per
9.3 si ha che
.
Definizione 9.7
Diremo che
![$ d$](img768.gif)
è
il massimo comun divisore di
![$ n$](img2.gif)
e
![$ m$](img218.gif)
se
è un massimo comun divisore positivo. La proposizione precedente
garantisce che se esiste il massimo comun divisore è unico. Esso
verrà indicato con
![$ (n,m)$](img778.gif)
.
Teorema 9.8
Dati due numeri
![$ n,m\in\mathbb{Z}$](img629.gif)
non entrambi nulli esiste il massimo
comun divisore di
![$ n$](img2.gif)
ed
![$ m$](img218.gif)
.
Dimostrazione.
Si consideri l'insieme
.
dato che
(dato che
e
non sono entrambi nulli). Sia
, dimostriamo che
è il massimo comun divisore. Se
e
allora
e
, quindi
ossia
. Dimostriamo ora che
. Consideriamo la divisione
euclidea tra
e
ossia
con
, se
allora
è un elemento di
. Ciò è
assurdo perché
e
. Quindi
ossia
.
In modo analogo si prova che
.
Osservazione 9.9
Dalla dimostrazione precedente segue che dati
![$ n,m\in\mathbb{Z}$](img629.gif)
esistono
![$ x,y\in\mathbb{Z}$](img793.gif)
tali che
![$ (n,m)=nx+my$](img794.gif)
e che gli interi della forma
![$ nx+my$](img795.gif)
con
![$ x,y\in\mathbb{Z}$](img793.gif)
sono tutti e soli i multipli di
![$ (n,m)$](img778.gif)
.
Definizione 9.10
![$ n,m\in\mathbb{Z}$](img629.gif)
non entrambi nulli si dicono
coprimi se
![$ (n,m)=1$](img796.gif)
.
Dimostrazione.
e quindi
.
Proposizione 9.13 (algoritmo di Euclide)
Siano
![$ n,m\in\mathbb{Z}$](img629.gif)
,
![$ m\ne 0$](img220.gif)
. Sia
![$ n= mq + r$](img653.gif)
la divisione euclidea di
![$ n$](img2.gif)
per
![$ m$](img218.gif)
allora
![$ \{c\in\mathbb{Z}\mid c\mathrel{\big\vert}n$](img804.gif)
e
![$ c\mathrel{\big\vert}
m\}=\{c\in\mathbb{Z}\mid c\mathrel{\big\vert}m$](img805.gif)
e
![$ c\mathrel{\big\vert}r\}$](img806.gif)
, in
particolare quindi
![$ (n,m)=(m,r)$](img807.gif)
.
Dimostrazione.
Se
e
allora
e
e quindi
ossia
e
. Viveversa
se
e
allora
e
e quindi
ossia
e
.
Osservazione 9.14
La proposizione precedente assieme all'osservazione che
![$ (n,0)=n$](img814.gif)
per
ogni
![$ n\ne 0$](img215.gif)
permette di costruire un algoritmo (
algoritmo di
Euclide) per il calcolo del M.C.D.
tale algoritmo si può tradurre in un programma ricorsivo per la definizione di
una funzione
MCD che calcoli il M.C.D. tra due numeri naturali:
Next: Lezione 10
Up: Matematica Discreta (II modulo)
Previous: Lezione 8
Domenico Luminati
2004-03-18