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.
Vediamo qual è il massimo comune divisore (MCD) dei numeri 53.667 e 25.527:
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.
Quindi il massimo comune divisore dei due numeri è l'ultimo resto (diverso da zero, ovviamente).
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.
Ad esempio, cerchiamo mcd (87, 41):
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.
Perché la risposta è un divisore dei valori 'a' e 'b' iniziali?
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'.
Perché la risposta è uguale al MCD?
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'applicazione dell'algoritmo di Euclide per più di due 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.
l'algoritmo di Euclide: trova il minimo comune multiplo (mcm) per grandi numeri
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.
Prova per la formula mcm
Il minimo comune multiplo, formula: mcm (a; b) = (a × b) / mcd (a; b);
Diciamo che le scomposizioni in fattori primi di 'a' e 'b' sono:
a = m × n × p, dove m, n, p - qualsiasi numero primo
b = m × q × t, dove m, q, t - qualsiasi numero primo