Cosa è il massimo comune divisore

In questo articolo parleremo del massimo comune divisore e di come calcolarlo.

Partiamo con la definizione: il massimo comune divisore di due numeri è il divisore più grande che i due numeri hanno in comune. Sembra una definizione articolata, ma in realtà si riferisce ad un concetto relativamente semplice (sempre se vi piace la matematica! xD) Partiamo allora con un esempio.

Supponiamo di voler calcolare il massimo comune divisore di 34 e 12. Se ci rifiutiamo di usare i numeri con la virgola, possiamo scrivere il numero 12 in tre modi differenti:

Come potete notare, abbiamo usato i numeri 1, 2, 3, 4, 6 e 12. Questi numeri sono chiamati i divisori di 12.

Anche il 34 può essere scritto come prodotto di numeri senza la virgola:

In questo caso abbiamo usato i numeri 1, 2, 17 e 34. Questi quattro numeri sono i divisori di 34.

Ritorniamo ora alla definizione di massimo comune divisore che abbiamo dato all’inizio di questo articolo. I numeri 34 e 12 hanno in comune i seguenti divisori: 1 e 2. Il massimo comune divisore di 34 e 12 è quindi 2.

Facciamo un altro esempio: qual è il massimo comune divisore di 27 e 9? Per rispondere a questa domanda dobbiamo, come prima:

  1. calcolare i divisori di 27
  2. calcolare i divisori di 9
  3. elencare i divisori che 27 e 9 hanno in comune
  4. il numero più grande tra quelli del punto precedente è il massimo comune divisore di 27 e 9

Punto 1) Calcoliamo i divisori di 9. Il numero 9 può essere scritto in due modi differenti:

I divisori di 9 sono quindi 1, 3 e 9.

Punto 2) Calcoliamo i divisori di 27. Anche il numero 27 può essere scritto in due modi differenti:

Pertanto, i divisori di 27 sono 1, 3, 9 e 27.

Punto 3) Elenchiamo i divisori che 27 e 9 hanno in comune. Sono tre i divisori che 27 e 9 hanno in comune: 1, 3 e 9.

Punto 4) Calcoliamo il massimo comune divisore. Il numero più grande tra 1, 3 e 9 è il 9, pertanto il massimo comune divisore tra 27 e 9 è 9.

Il metodo descritto sopra può essere utilizzato per calcolare il massimo comune divisore di due numeri molto grandi? Dipende. Se abbiamo già fattorizzato i due numeri, allora possiamo calcolare il loro massimo comune divisore utilizzando il metodo di questo articolo. (Abbiamo parlato della fattorizzazione un paio di mesi fa: per ogni dubbio vi rimando a questo articolo). Se invece non sapete come fattorizzare i due numeri (e questo è il caso che accade più spesso in crittografia, anzi direi quasi sempre!) allora NON potere utilizzare il metodo di questo articolo per calcolare il massimo comune divisore (sembra triste ma è così!)

Per fortuna esiste un metodo (chiamato “di Euclide” in onore del matematico che lo inventò) che permette di calcolare il massimo comune divisore velocemente e in ogni occasione (anche mentre siete fuori a cena: bastano carta e penna! xD). Scherzi a parte, potete usare il metodo di Euclide addirittura per calcolare il massimo comune divisore di due numeri di 100 cifre ciascuno! In tal caso il vostro computer non impiegherà molto tempo per calcolare il risultato (e vi ringrazierà anche, perché l’ultima volta gli avete chiesto di fattorizzare un numero gigante e lo avete mandato in crash! xD)

Nel prossimo articolo parleremo del metodo di Euclide per il calcolo del massimo comune divisore. Nel frattempo scrivete pure nei commenti se avete domande o dubbi riguardanti il massimo comune divisore. Buona crittografia! xD