Numeri primi e Massimo Comun Divisore

Nel post dedicato alla fattorizzazione abbiamo visto che un numero naturale è scomponibile in serie di fattori e che le operazioni di prodotto e divisione tra interi, sono riconducibili ad operazioni sugli insiemi, stabilendo quindi una corrispondenza tra:

•     moltiplicazione tra interi e unione di insiemi di fattori
•     divisione tra interi e differenza di insiemi di fattori

Un’altra operazione fondamentale tra interi è il Massimo Comun Divisore. L’MCD di due numeri interi è

il numero più grande possibile che li divide entrambe.

Una volta costruta la scomposizione in fattori di un numero, l’elenco dei divisori è concettualmente semplice da costruire. Riprendiamo ad esempio la scomposizione di 18:

F(18) = {2, 3, 3}

i divisori di un numero sono rappresentati da tutte le combinazioni possibili dei prodotti dei suoi fattori. Sono quindi divisori di 18:

2, 3, 2×3 = 6, 3×3 = 9

Prendiamo ora il numero 12:

F(12) = {2, 2, 3}

sono divisori del 12:

2, 3, 2×2 = 4, 2×3 = 6

Il Massimo Comun Divisore di 12 e 18 è quindi 6.

La volta scorsa abbiamo introdotto una notazione insiemistica un pò “allargata”, per così dire, dove ammettiamo la ripetizione degli elementi. Nei fattori di 12, ad esempio, ci sono due 2 e in quelli di 18 due 3. Con questo artificio possiamo costruire il Massimo Comun Divisore in modo estremamente semplice, ed elegante:

MCD(N, M) = F(N)  F(M)

dove è il simbolo insiemistico di intersezione, che corrisponde a prendere gli elementi comuni dei due insiemi.

Comprendere questa definizione è semplice: l’MCD è definito come il divisore più grande comune a due numeri, ma ciò equivale a richiedere che tutti i fattori dell’MCD compaiano sia nel primo che nel secondo numero. E’ l’esatta definizione dell’operazione di intersezione insiemistica.

Abbiamo quindi aggiunto una ulteriore relazione di corrispondenza tra operazione sugli interi e operazioni sugli insiemi:

• moltiplicazione tra interi / unione di insiemi di fattori
• divisione tra interi / differenza di insiemi di fattori
• MCD tra interi / intersezione di fattori

Questa formalizzazione ci consente di ricavare diverse proprietà dell’MCD senza necessariamente far di conto, ad esempio.

Il Massimo Comun Divisore di un numero con sé stesso è uguale allo stesso numero:

MCD(N, N) = F(N) F(N) = F(N)

perché un insieme intersecato con sé stesso é uguale a sé stesso.

Ma lo spunto più interessante è che possiamo far di conto senza effettivamente calcolare le divisioni, semplicemente aggiungendo, rimuovendo o determinando le intersezioni di insiemi. Osservate come in questa serie di post non sia stata citata né minimamente eseguita alcuna divisione. Torneremo sulle proprietà dell’MCD a strettissimo giro, dimostrando come sia possibile calcolarlo semplicemente mediante una sequenza di sottrazioni.

Iniziate a tirar fuori dalla Borsa del Matematico uno strumento che ci è stato utile già diverse volte: la ricorsione.