Algoritmo di Euclide per i grandi numeri, metodo di calcolo per MCD e MCM

Trova il massimo comune divisore (MCD) per i grandi numeri

Per i grandi numeri, la scomposizione in fattori primi è difficile. Se vogliamo stabilire il massimo comune divisore (MCD) di alcuni grandi numeri simili, allora si utilizzerà un metodo che non usa la scomposizione in fattori primi, ma utilizzerà l'algoritmo di Euclide... vedi l'esempio sotto.

Questo algoritmo prevede l'operazione di divisione e calcolo dei resti.
'a' e 'b' sono i due numeri interi positivi, 'a' >= 'b'.
Dividi 'a' per 'b' e ottieni il resto, 'r'.
Se 'r' = 0, STOP. 'b' = il MCD di 'a' e 'b'.
Altrimenti: Sostituisci ('a' con 'b') e ('b' con 'r'). Torna al passaggio della divisione, sopra.

1) 53.667 = 25.527 × 2 + 2.613 (divido il numero più grande con il numero più piccolo)
2) 25.527 = 2.613 × 9 + 2.010 (divido il numero più piccolo al resto dell'operazione di sopra)
3) 2.613 = 2.010 × 1 + 603 (divido il resto della prima operazione con il resto della seconda operazione)
4) 2.010 = 603 × 3 + 201 (divido il resto della seconda operazione con il resto della terza operazione)
5) 603 = 201 × 3 (divido il resto della terza operazione con il resto della quarta operazione); in questo momento, non avendo più resto, ci fermiamo, 201 è il numero cercato.

Se quest'ultimo resto è uguale a uno, allora i due numeri sono primi tra di loro.
Per le operazioni menzionate sopra, l'ultimo divisore, 201 è il massimo comune divisore (MCD) dei numeri 53.667 e 25.527.
Possiamo dimostrare con l'aiuto dell'algoritmo di Euclide anche il fatto che due numeri sono primi tra di loro.

1) 87 = 41 × 2 + 5 (divido il numero più grande con il numero più piccolo)
2) 41 = 5 × 8 + 1 (divido il numero più piccolo con il resto dell'operazione di sopra)
3) 5 = 5 × 1 + 0 (divido il resto della prima operazione con il resto della seconda operazione, che però è uno, l'operazione non avrà più resto)
L'ultimo resto diverso da zero delle operazioni di sopra è uguale a 1.
mcd (87, 41) = 1, quindi i numeri sono primi tra di loro.

Nota: 'a' : 'b' = 'q' + 'r' è equivalente all'equazione: 'a' = 'q' × 'b' + 'r', dove 'q' è il quoziente dell'operazione.
Quando il valore finale di 'r' = 0, il valore finale di 'b' è un divisore del valore finale di 'a', poiché 'a' = 'q' × 'b' + 0.
Torna indietro in ciascuno dei passaggi precedenti e analizza ciascuna equazione, 'a' = 'q' × 'b' + 'r', e nota che ad ogni passaggio il valore finale di 'b' è un divisore di ogni valore di 'r' e di ogni valore di 'b' e quindi è un divisore di ogni valore di 'a'. Quindi l'ultimo valore di 'b', che è l'ultimo resto diverso da zero, è un divisore dei valori iniziali di 'a' e 'b'.

Guarda tutte le equazioni: 'a' = 'q' × 'b' + 'r'. Come abbiamo visto sopra, il valore finale di 'b' è un divisore di tutti i valori di 'a', 'b' e 'r'.
Quindi il valore finale di 'b' deve essere anche un divisore dell'ultimo valore di 'r', quello che è diverso da zero. E il valore finale di 'b' non può essere maggiore dell'ultimo valore di 'r'. Poiché il valore finale di 'b' è uguale all'ultimo valore di 'r', quindi il valore finale di 'b' è il più grande divisore dei valori iniziali di ('a' e 'b'). E per definizione è chiamato il massimo comune divisore dei numeri.

L'algoritmo di Euclide si può utilizzare anche per trovare il massimo comune divisore (mcd) per più numeri, ad esempio a, b e c. Si procederà in due tappe. Per primo troveremo il mcd (a, b) = d e poi troveremo il mcd (c, d) = e.

Nella situazione dei numeri più grandi diventa scomodo da calcolare il minimo comune multiplo (mcm), perché la scomposizione in fattori primi richiede più tempo.
Con l'aiuto dell'algoritmo di Euclide si trova il massimo comune divisore (mcd) - vedi di sopra, ma anche il minimo comune multiplo (mcm), secondo la regola:
mcm (a, b) = (a × b) / mcd(a, b);
Questo metodo non si può estendere a più di due numeri.