Minimo comune multiplo e massimo comun divisore

Obiettivo (corso Analisi Matematica 1)

Ripasso sul minimo comune multiplo
Massimo Comun Divisore
Numeri pari e dispari
Esempi

Il minimo comune multiplo: $\operatorname {mcm}$

Dati due numeri $a$ e $b$ il minimo comune multiplo $\operatorname {mcm}(a,b)$ è definito come il più piccolo numero intero positivo multiplo di entrambi

si generalizza facilmente a più numeri
si calcola a partire dalla scomposizione in fattori primi dei numeri
è il prodotto di tutti i fattori primi (comuni e non comuni), presi una sola volta con il massimo esponente

Esempio di $\operatorname{mcm}$

Calcolare il $\operatorname {mcm}(12,\ 280,\ 900)$

Passo 1: calcolo della fattorizzazione in numeri primi

$12\;=\;4\times 3 \;=\; 2^2\times 3$
$280\;=\; 28 \times 10 \;=\; (7\times4) \times (5\times2) \;=\;2^3\times 5\times 7$
$900\;=\; 9 \times 100 \;=\; 9 \times (25\times4) \;=\; 2^2\times 3^2 \times 5^2$

Passo 2: calcolo del m.c.m.

Tutti i fattori primi con il massimo esponente

$$\begin{aligned} \operatorname {mcm}(12,\ 280,\ 900) &=\; 2^3\times 3^2 \times 5^2 \times 7 \\ &=\; 8 \times 9 \times 25\times 7 \\ &=\; 12600 \end{aligned}$$

Il massimo comun divisore: $\operatorname {MCD}$

Dati due numeri $a$ e $b$ il massimo comun divisore $\operatorname {MCD}(a,b)$ è definito come il numero naturale più grande per il quale possono essere divisi entrambi

si generalizza facilmente a più numeri
si calcola a partire dalla scomposizione in fattori primi dei numeri
è il prodotto di tutti i fattori primi comuni considerati una sola volta con il loro esponente più piccolo

Esempio di $\operatorname{MCD}$

Calcolare il $\operatorname {MCD}(12,\ 280,\ 900)$

Passo 1: calcolo della fattorizzazione in numeri primi

$12=2^2\times 3$
$280=2^2\times 2\times 5\times 7$
$900=2^2\times 3^2 \times 5^2$

Passo 2: calcolo del M.C.D.

Tutti i fattori primi comuni con l'esponente più piccolo

$$ \operatorname {MCD}(12,\ 280,\ 900) \;=\; 2^2 \;=\; 4 $$

Esercizio

Calcolare il $\operatorname {mcm}$ e $\operatorname {MCD}$ di $24,\ 84,\ 144$

Passo 1: calcolo della fattorizzazione in numeri primi

$24 \;=\; 4 \times 6 \;=\; 2 \times 2 \times 2 \times 3 \;=\; 2^2\times 2 \times 3$
$84 \;=\; 4 \times 21 \;=\; 2 \times 2 \times 3 \times 7 \;=\; 2^2\times 3 \times 7$
$144 \;=\; 3 \times 48 \;=\; 3 \times 6 \times 8 = 2^2 \times 2^2\times 3 \times 3$

Passo 2: calcolo del m.c.m. e M.C.D.

$\operatorname {mcm}(24,\ 84,\ 14) \;=\;2^4\times 3^2\times 7\;=\; 1008$
$\operatorname {MCD}(24,\ 84,\ 14) \;=\;2^2\times 3\;=\; 12$

Numeri coprimi

Due numeri $a$ e $b$ si dicono coprimi se il $\operatorname {MCD}(a,b)=1$

Ad esempio, $4$ e $9$ sono coprimi tra loro in quanto le due fattorizzazioni

$4\;=\; 2^2$
$9 \;=\; 3^2$

non hanno nessun primo in comune e quindi il $\operatorname {MCD}(4,\ 9)=1$

Numeri pari e dispari

L'insieme dei numeri pari $$\big\{0,\ 2,\ 4,\ 6,\ \ldots\ \big\}$$ può essere scritto come $$ \big\{2k:k\in \mathbb{N} \big\}$$

L'insieme dei numeri dispari $$\big\{1,\ 3,\ 5,\ 7,\ \ldots\ \big\}$$ può essere scritto come $$\big\{2k+1:k\in \mathbb{N} \big\}$$

L'algoritmo di Euclide

Permette di calcolare il $\operatorname {MCD}(a,b)$
Non si basa sulla fattorizzazione in numeri primi di $a$ e $b$
Si parte con la condizione $a>b$
L'idea è che se $\operatorname {MCD}(a,b)$ divide sia $a$ che $b$ allora divide anche la differenza $a-b$ e quindi si ha la formula di ricorrenza $$ \operatorname {MCD}(a,b) = \operatorname {MCD}(b, r) $$ dove $a = qb + r$
Il $\operatorname {mcm}(a,b)$ si calcola dalla relazione $$ a\cdot b = \operatorname {MCD}(a,b) \cdot \operatorname {mcm}(a,b) $$

L'algoritmo di Euclide (esempio)

Calcolare $\operatorname {MCD} (84, 24)$ e $\operatorname {mcm} (24, 12)$

$\operatorname {MCD} (84, 24)$
Ora $84 = 3\times 24 + 12$
$\operatorname {MCD} (24, 12)$
Ora $24 = 2\times 12 + 0$
$\operatorname {MCD} (12, 0) \implies 12$
$\operatorname {mcm} (24, 12) \;=\; {84 \cdot 24 \over 12} \;=\; 84\times 2 = 168$

Ricorda di sostenere questo progetto con una donazione (PayPal.Me/ManoloVenturin).