Massimo comune divisore e minimo comune multiplo

Il massimo comune divisore e il minimo comune multiplo

Nella lezione su divisibilità e divisione con resto si è studiata la relazione $d \mid a$ tra due naturali. Quando si considerano due numeri insieme, interessano i divisori che hanno in comune e i multipli che condividono. Ogni coppia di naturali $a$ e $b$ ha almeno un divisore comune, l’$1$, e al più un numero finito di essi, perché nessun divisore di $a$ supera $a$; ha, inoltre, infiniti multipli comuni, tra cui il prodotto $ab$. Se è così, la definizione seguente ha senso.

Definizione (massimo comune divisore e minimo comune multiplo). Il massimo comune divisore di due naturali $a$ e $b$, che si scrive $\operatorname{MCD}(a, b)$, è il più grande naturale che li divide entrambi. Il minimo comune multiplo, che si scrive $\operatorname{mcm}(a, b)$, è il più piccolo naturale che è multiplo di entrambi.

Il secondo è il minimo di un insieme non vuoto di naturali, che esiste per il principio del buon ordinamento. Il primo è il massimo dell’insieme dei divisori comuni, che non è vuoto ed è limitato da $a$; che un insieme non vuoto di naturali limitato superiormente abbia massimo segue anch’esso dal buon ordinamento: l’insieme dei suoi maggioranti non è vuoto e ha un minimo $M$, e $M$ appartiene all’insieme, perché altrimenti ogni elemento sarebbe minore di $M$ e, poiché non ci sono naturali tra $M - 1$ e $M$, non maggiore di $M - 1$, che sarebbe un maggiorante minore di $M$ (se $M = 1$, l’insieme è $\{1\}$ e contiene $M$). Per esempio, i divisori comuni di $12$ e $18$ sono $1$, $2$, $3$ e $6$, e i loro multipli comuni sono $36$, $72$, $108$, e così via:

Dalla definizione seguono immediatamente alcuni casi particolari: $\operatorname{MCD}(a, 1) = 1$ e $\operatorname{mcm}(a, 1) = a$; $\operatorname{MCD}(a, a) = \operatorname{mcm}(a, a) = a$; e, se $a$ divide $b$, allora $\operatorname{MCD}(a, b) = a$ e $\operatorname{mcm}(a, b) = b$. Entrambe le operazioni sono, inoltre, simmetriche: l’ordine dei numeri non altera il risultato.

Calcolo mediante la scomposizione in fattori primi

Per il teorema fondamentale dell’aritmetica, ogni naturale maggiore di $1$ si scompone in modo unico in fattori primi. Conviene scrivere $a$ e $b$ con gli stessi primi $p_1, \ldots, p_k$, ammettendo esponenti nulli per i primi che compaiono solo in uno dei due:

Un naturale $d$ divide $a$ esattamente quando nella sua scomposizione non compaiono primi diversi da quelli di $a$, e ciascuno con esponente non maggiore di quello che ha in $a$. Ne segue che $d$ divide sia $a$ sia $b$ quando l’esponente di ogni primo in $d$ non supera nessuno dei due esponenti; il massimo divisore comune si ottiene, quindi, prendendo per ogni primo il minore dei due esponenti. Allo stesso modo, $m$ è multiplo comune quando l’esponente di ogni primo in $m$ raggiunge entrambi, e il minimo multiplo comune prende per ogni primo il maggiore dei due esponenti. Per esempio:

Il metodo è chiaro, ma dipende dal saper fattorizzare, e fattorizzare numeri grandi è molto costoso: non si conosce alcun procedimento rapido per farlo. L’algoritmo della sezione seguente calcola il massimo comune divisore senza fattorizzare, con sole divisioni.