Massimo Comune Divisore
Il Massimo Comune Divisore ( M.C.D. ) è il più alto numero intero d divisore di due interi a e b diversi da zero. Si indica con $$ MCD(a,b) $$ oppure semplicemente $$ (a,b) $$
Dal punto di vista pratico il massimo comune divisore di due numeri è il prodotto dei fattori primi in comune, presi una sola volta con l'esponente più piccolo.
Esempio. Per calcolare il M.C.D. di 30 e 40 scompongo i due numeri in fattori primi $$ 30 = 2 \cdot 3 \cdot 5 $$ $$ 40 = 2^3 \cdot 5 $$ I fattori primi in comune con esponente più basso sono 2 e 5. Pertanto, il massimo comune divisore è 2·5=10. $$ MCD(30,40) = 2 \cdot 5 = 10 $$
Dati due interi a e b dell'insieme Z, un elemento d di Z si dice massimo comune divisore di a e b, se
- L'intero d è un divisore di a e b. $$ d|a ∧ d|b $$
- Se esiste un altro intero c divisore di a e b, allora c divide anche d $$ \forall \ c \in Z : c|a ∧ c|b \rightarrow c|d $$
Nota. Sarebbe più corretto parlare di "un" massimo comune divisore, perché d è una classe di equivalenza che contiene gli elementi associati d e -d. Generalmente, quando si parla "del" massimo comune divisore si intende soltanto l'intero positivo d.
Un esempio pratico
Dati due numeri interi a=12 e b=8
$$ a=12 \\ b=8 $$
I divisori comuni di a e b sono
$$ 1, 2, 4 $$
Pertanto, il massimo comune divisore è 4.
$$ MCD(12,8)=4 $$
Come calcolare il massimo comune divisore
Un metodo per calcolare il massimo comune divisore consiste nella scomposizione in fattori primi dei due numeri. Poi si scelgono i fattori in comune con l'esponente più basso.
Esempio
Dati due interi a=8 e b=48
$$ a=8 \\ b=48 $$
I fattori primi dei due numeri sono
$$ \begin{array}{c|c} a & f \\ \hline 8 & 2 \\ 4 & 2 \\ 2 & 2 \\ 1 & 1 \end{array} $$
$$ \begin{array}{c|c} b & f \\ \hline 48 & 2 \\ 24 & 2 \\ 12 & 2 \\ 6 & 2 \\ 3 & 3 \\ 1 & 1 \end{array} $$
Quindi
$$ a=8= 2 \cdot 2 \cdot 2 \cdot 1= 2^3 $$
$$ b=24= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 1 = 2^4 \cdot 3 $$
Seleziono i fattori in comune (2) con esponente più basso ossia 23.
$$ 2^3 $$
Quindi, il massimo comune divisore è il seguente
$$ MCD(8,48) = 8 $$
Nota. Questo metodo funziona per i numeri molto piccoli. Diventa complesso e poco pratico da utilizzare quando i numeri interi sono molto alti, perché occorre scomporre i due numeri in fattori primi. In quest'ultimo caso è preferibile usare l'algoritmo di Euclide.
Le proprietà del massimo comune divisore
Il massimo comune divisore di due interi gode delle seguenti proprietà:
$$ MCD(a,b)=MCD(b,a) $$
Esempio $$ MCD(12,8)=MCD(8,12)=4 $$
$$ MCD(a,b)=MCD(|a|,|b|) $$
Esempio $$ MCD(12,8)=MCD(-12,-8)=MCD(-12,8)=MCD(12,-8)=4 $$
$$ MCD(a,b)=MCD(k \cdot a,k \cdot b) $$
Esempio $$ MCD(12,8)=MCD(k \cdot 12, k \cdot 8)=4 $$
$$ MCD(ak,bk)=|k| \cdot MCD(a,b) $$
Esempio $$ MCD(12k,8k)=|k| \cdot MCD(12, 8)=|k| \cdot 4 $$
$$ MCD(a,0)=MCD(a,0)=|a| \:\:\: \forall a \ne 0 $$
Esempio $$ MCD(12,0)=|12| $$
La divisione per zero non è definita nell'insieme dei numeri interi. Pertanto, non si può calcolare il massimo comune divisore MCD(0,0).
Interi relativamente primi
Due interi a e b sono detti relativamente primi o primi tra loro se il massimo comune divisore è uguale a uno $$ MCD(a,b)=1 $$
Quando due numeri hanno il MCD uguale a 1 vuol dire che i due numeri non hanno divisori in comune.
Esempio
Il massimo comune divisore di 4 e 5 è uguale a 1.
$$ MCD(4,5)=1 $$
Pertanto, gli interi 4 e 5 sono relativamente primi.
Nota. I numeri relativamente primi non è detto che siano anche numeri primi. Ad esempio, i numeri 8 e 9 sono relativamente primi perché non hanno divisori in comune (8=2^3 e 9=3^2) ma non sono numeri primi. $$ MCD(8,9)=1 $$
La differenza tra massimo comune divisore (MCD) e minimo comune multiplo (mcm)
Il massimo comune divisore (MCD) e il minimo comune multiplo (mcm) di due interi a e b sono legati tra loro dalla seguente relazione. $$ mcm(a,b)=\frac{|ab|}{MCD(a,b)} $$
Esempio
Dati due interi a=8 e b=12
$$ mcm(8,12)=24 $$
$$ MCD(8,12)=4 $$
Verifico se la precedente relazione è soddisfatta.
$$ mcm(a,b)=\frac{|ab|}{MCD(a,b)} $$
$$ mcm(8,12)=\frac{|8 \cdot 12|}{MCD(8,12)} $$
$$ 24=\frac{96}{4} $$
$$ 24=24 $$
La relazione tra mcm e MCD è soddisfatta.
L'identità di Bézout
Il massimo comune divisore di due interi a e b può essere scritto come combinazione lineare di altri due interi j e k.
$$ MCD(a,b)=d=aj+bk $$
Questa forma è detta identità di Bézout.
E così via.
