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.

Vediamo qual è il massimo comune divisore (MCD) dei numeri 53.667 e 25.527:

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):

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.

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.


Che cosa è un numero primo?

Che cosa è un numero composto?

I numeri primi fino a 1.000

I numeri primi fino a 10.000

Il crivello di Eratostene

Algoritmo di Euclide

Riduci (semplifica) le frazioni ordinarie matematiche ai minimi termini: misure e di esempi