Calcolatore di MCD — Massimo Comune Divisore

Il calcolatore di MCD valuta il massimo comune divisore tra due fino a quindici numeri diversi. Continua a leggere per trovare la risposta alla domanda "Qual è il massimo comune divisore di numeri dati?", scoprire diversi metodi di calcolo dell'MCD, tra cui la scomposizione in fattori primi o l'algoritmo di Euclide— decidi tu qual è il tuo preferito. Vedrai che il nostro calcolatore di MCD può farti risparmiare tempo quando hai a che fare con numeri grandi!

Il massimo comune divisore è il più grande fattore intero di un insieme di numeri. Il massimo comune divisore è importante in alcune applicazioni della matematica come la semplificazione dei polinomi, dove spesso è essenziale scomporre in fattori. Quindi, dobbiamo sapere come trovare l'MCD.

Esistono diversi metodi che ti aiutano a trovare l'MCD. Alcuni sono un gioco da ragazzi, mentre altri sono più complessi. Vale la pena conoscerli tutti per poter decidere quale preferisci:

• Lista di fattori;
• Scomposizione dei numeri in fattori primi;
• Algoritmo di Euclide;
• Algoritmo binario (algoritmo di Stein); e
• Diverse proprietà dell'MCD (incluso il minimo comune multiplo, mcm).

La buona notizia è che puoi stimare l'MCD con semplici operazioni matematiche senza radici o logaritmi! Nella maggior parte dei casi si tratta solo di sottrazione, moltiplicazione o divisione.

Il metodo principale utilizzato per stimare il massimo comune divisore consiste nel trovare tutti i fattori dei numeri dati. I fattori sono semplicemente numeri che vengono moltiplicati tra loro per ottenere il valore originale. In generale, possono essere sia positivi che negativi, ad esempio 2 × 3 è uguale a (-2) × (-3), entrambi uguali a 6. Da un punto di vista pratico, consideriamo solo quelli positivi. Inoltre, ci interessano solo i numeri interi. Altrimenti, potresti trovare una combinazione infinita di frazioni distinte che sono fattori del numero dato, il che è inutile nel nostro caso. Sapendo questo, stimiamo il massimo comune divisore dei numeri 72 e 40:

1. I fattori di 72 sono: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72;
2. I fattori di 40 sono: 1, 2, 4, 5, 8, 10, 20, 40;
3. Elenca tutti i fattori comuni: 1, 2, 4, 8; e
4. Il massimo comune divisore è 8, il valore più alto dell'elenco precedente.

Proviamo a fare qualcosa di più impegnativo. Vogliamo trovare la risposta alla domanda: "Qual è il massimo comune divisore di 33 264 e 35 640?" Tutto ciò che dobbiamo fare è ripetere i passaggi precedenti:

1. I fattori di 33 264 sono: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1008, 1188, 1232, 1386, 1512, 1584, 1848, 2079, 2376, 2772, 3024, 3696, 4158, 4752, 5544, 8316, 11 088, 16 632, 33 264;

2. I fattori di 35 640 sono: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1080, 1188, 1320, 1485, 1620, 1782, 1980, 2376, 2970, 3240, 3564, 3960, 4455, 5940, 7128, 8910, 11 880, 17 820, 35 640;

3. Ecco l'elenco di tutti i divisori comuni: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1188, 2376; e

4. Il risultato finale è: 2376.

Come puoi vedere, più alto è il numero di fattori, più la procedura richiede tempo ed è facile commettere errori. Vale la pena sapere come funziona questo metodo, ma ti consigliamo di utilizzare il nostro calcolatore di MCD per assicurarti che il risultato sia corretto.

Un'altra procedura comunemente utilizzata per calcolare il massimo comune divisore utilizza la scomposizione in fattori primi 🇺🇸, chiamata anche fattorizzazione in numeri primi. Questo metodo è in qualche modo correlato a quello precedente. Invece di elencare tutti i fattori possibili, troviamo solo quelli che sono numeri primi. Di conseguenza, il prodotto di tutti i numeri primi condivisi è la risposta al nostro problema e, cosa ancora più importante, esiste sempre un unico modo per fattorizzare qualsiasi numero in numeri primi. Troviamo quindi il massimo comune denominatore di 72 e 40 utilizzando la scomposizione in fattori primi:

1. I fattori primi di 72 sono: 2, 2, 2, 3, 3;

2. I fattori primi di 40 sono: 2, 2, 2, 5;

3. In altre parole, possiamo scrivere: 72 = 2 × 2 × 2 × 3 × 3 e 40 = 2 × 2 × 2 × 5; e

4. La parte condivisa in entrambi i casi è 2 × 2 × 2 = 8 e questo è il massimo comune divisore.

Possiamo notare che per questo semplice esempio, il risultato è coerente con il metodo precedente. Scopriamo se funziona altrettanto bene per un caso più complicato. Qual è l'MCD di 33 264 e 35 640?

1. I fattori primi di 33 264 sono: 2, 2, 2, 2, 3, 3, 3, 7, 11;

2. I fattori primi di 35 640 sono: 2, 2, 2, 3, 3, 3, 3, 5, 11;

3. Possiamo usare la notazione esponenziale per scrivere i prodotti come segue: 33 264 = 2⁴ × 3³ × 7 × 11, 35 640 = 2³ × 3⁴ × 5 × 11, e

4. Il fattore primo comune dei due numeri è 2³ × 3³ × 11. Possiamo anche scriverlo in modo più compatto e sofisticato, usando i fattoriali: (3!)³ × 11. Controlla se il nostro calcolatore di MCD ti dà lo stesso risultato, ovvero 2376.

L'idea alla base dell'algoritmo di Euclide dice che se il numero k è il massimo comune divisore dei numeri A e B, allora k è anche l'MCD della differenza di questi numeri, A - B. Seguendo questa procedura, arriveremo infine a 0. Di conseguenza, il massimo comune divisore è l'ultimo numero non nullo. Vediamo ancora una volta i nostri esempi — i numeri 40 e 72. Ogni volta che effettuiamo una sottrazione, confrontiamo due numeri ordinandoli dal valore più alto a quello più piccolo:

• MCD di 72 e 40: la differenza 72 - 40 è uguale a 32;
• MCD di 40 e 32: 40 - 32 = 8;
• MCD di 32 e 8: 32 - 8 = 24;
• MCD di 24 e 8: 24 - 8 = 16;
• MCD di 16 e 8: 16 - 8 = 8; e
• MCD di 8 e 8: 8 - 8 = 0 STOP!

Nell'ultimo passaggio, otteniamo 0 dalla sottrazione. Questo significa che troviamo il nostro massimo comune divisore e il suo valore nella penultima riga delle sottrazioni: 8.

Che ne dici di prendere un caso più difficile: 33 264 e 35 640? Proviamo a risolverlo utilizzando l'algoritmo di Euclide:

• MCD di 35 640 e 33 264: 35 640 - 33 264 = 2376;
• MCD di 33 264 e 2376: 33 264 - 2376 = 30 888;
• MCD di 30 888 e 2376: 30 888 - 2376 = 28 512;
• MCD di 28 512 e 2376: 28 512 - 2376 = 26 136;
• MCD di 26 136 e 2376: 26 136 - 2376 = 23 760;
• MCD di 23 760 e 2376: 23 760 - 2376 = 21 384;
• MCD di 21 384 e 2376: 21 384 - 2376 = 19 008;
• MCD di 19 008 e 2376: 19 008 - 2376 = 16 632;
• MCD di 16 632 e 2376: 16 632 - 2376 = 14 256;
• MCD di 14 256 e 2376: 14 256 - 2376 = 11 880;
• MCD di 11 880 e 2376: 11 880 - 2376 = 9504;
• MCD di 9504 e 2376: 9504 - 2376 = 7128;
• MCD di 7128 e 2376: 7128 - 2376 = 4752;
• MCD di 4752 e 2376: 4752 - 2376 = 2376; e
• MCD di 2376 e 2376: 2376 - 2376 = 0 STOP!

Analogamente all'esempio precedente, l'MCD di 33 264 e 35 640 è l'ultima differenza non nulla della procedura, ovvero 2376.

Come puoi vedere, la versione di base di questo calcolatore di MCD è molto efficace e semplice, ma presenta uno svantaggio significativo. Più grande è la differenza tra i numeri dati, più passaggi sono necessari per raggiungere il passo finale. Il modulo è un'operazione matematica efficace che risolve il problema, perché siamo interessati solo a un resto inferiore a entrambi i numeri. Ripetiamo l'algoritmo di Euclide per i nostri esempi utilizzando il modulo invece della normale sottrazione:

• MCD di 72 e 40: 72 mod 40 = 32;
• MCD di 40 e 32: 40 mod 32 = 8; e
• MCD di 32 e 8: 32 mod 8 = 0 STOP!

Il grande comune divisore è 8. E l'altro esempio?

• MCD di 35 640 e 33 264: 35 640 mod 33 264 = 2376; e
• MCD di 33 264 e 2376: 33 264 mod 2376 = 0 STOP!

L'MCD di 35 640 e 33 264 è 2376, ed è stato trovato in soli due passaggi invece che in 15. Non male, vero?

Se ti piacciono operazioni aritmetiche più semplici di quelle utilizzate nell'algoritmo di Euclide (ad esempio il modulo), l'algoritmo binario (o algoritmo di Stein) fa decisamente al caso tuo! Tutto ciò che devi usare è il confronto, la sottrazione e la divisione per 2. Mentre stimi il massimo comune divisore di due numeri, tieni a mente queste identità:

1. MCD(A, 0) = A, stiamo usando il fatto che ogni numero divide zero e un'osservazione dell'ultimo passo dell'algoritmo di Euclide — uno dei numeri scende a zero e il nostro risultato è quello precedente;

2. Se A e B sono entrambi pari, significa che MCD(A, B) = 2 × MCD(A/2, B/2) grazie al fatto che 2 è un fattore comune;

3. Se solo uno dei numeri è pari, diciamo A, allora MCD(A, B) = MCD(A/2, B). Questa volta 2 non è un divisore comune, quindi possiamo continuare con la riduzione finché entrambi i numeri non sono dispari;

4. Se A e B sono entrambi dispari e A > B, allora MCD(A, B) = MCD((A-B)/2, B). Questa volta combiniamo due caratteristiche in un unico passaggio. La prima è derivata dall'algoritmo di Euclide, che elabora il massimo comune divisore tra la differenza dei due numeri e quello più piccolo. In secondo luogo, la divisione per 2 è possibile, dato che la differenza di due numeri dispari è pari e, in base al passaggio 3, possiamo ridurre il numero pari; e

5. I passaggi da 2 a 4 vengono ripetuti fino a raggiungere il passaggio 1 o se A = B. Il risultato sarà 2ⁿ × A, dove n è il numero di fattori 2 trovati nel secondo passaggio.

Come al solito, mettiamo in pratica l'algoritmo con i nostri insiemi di numeri. Iniziamo con 40 e 72:

• Sono entrambi pari quindi MCD(72, 40) = 2 × MCD(36, 20) = 2² × MCD(18, 10) = 2³ × MCD(9, 5) = ...;

• I numeri rimanenti sono dispari quindi ... = 2³ × MCD((9-5)/2, 5) = 2³ × MCD(2, 5);

• 2 è pari quindi possiamo ridurlo: ... = 2³ × MCD(1, 5);

• 1 e 5 sono dispari quindi: ... = 2³ × MCD((5-1)/2, 1) = 2³ × MCD(2, 1); e

• Rimuovi 2 da un numero pari: ... = 2³ × MCD(1, 1) = 2³ = 8.

In realtà, avremmo potuto fermarci al terzo passo, dato che l'MCD di 1 e di un numero qualsiasi è 1.
Ok, e come trovare il massimo comune divisore di 33 264 e 35 640 usando il metodo binario?

• Due numeri pari: MCD(35 640, 33 264) = 2 × MCD(17 820, 16 632) = 2² × MCD(8910, 8316) = 2³ × MCD(4455, 4158) = ...;

• Uno pari uno dispari: ... = 2³ × MCD(4455, 2079);

• Due dispari: ... = 2³ × MCD((4455-2079)/2, 2079) = 2³ × MCD(1188, 2079);

• Uno pari uno dispari: ... = 2³ × MCD(594, 2079) = 2³ × MCD(297, 2079);

• Due dispari: ... = 2³ × MCD((2079-297)/2, 297) = 2³ × MCD(891, 297); e

• Due dispari: ... = 2³ × MCD((891-297)/2, 297) = 2³ × MCD(297, 297) = 2³ × 297 = 2376.

Sappiamo che i numeri primi sono quelli che hanno solo 2 fattori interi positivi: 1 e se stesso. Quindi la domanda è "Cosa sono i numeri coprimi?" Possiamo definirli come numeri che non hanno fattori comuni. Più precisamente, 1 è il loro unico fattore comune, ma dato che omettiamo 1 nella scomposizione in fattori primi, possiamo dire che non hanno divisori comuni. In altre parole, possiamo dire che i numeri A e B sono coprimi se MCD(A,B) = 1. In realtà non significa che uno dei due sia un numero primo, ma solo che l'elenco dei fattori comuni è vuoto. Esempi di numeri coprimi sono: 5 e 7, 35 e 48, 23 156 e 44 613.

Cosa curiosa, è possibile calcolare la probabilità che due numeri scelti a caso siano coprimi. Anche se è piuttosto complicato, il risultato complessivo è di circa il 61%. Sorprendente, vero? Fai una prova — immagina due numeri a caso (diciamo di almeno 5 cifre), usa il nostro calcolatore di MCD e scopri se il risultato è 1 o no. Ripeti il gioco più volte e valuta qual è la percentuale di numeri coprimi che hai trovato.

Ora che conosciamo numerosi metodi per trovare il massimo comune divisore di due numeri, potresti chiederti "Come trovare il massimo comune divisore di tre o più numeri?". Non è così difficile come potrebbe sembrare a prima vista. Elencare tutti i fattori di ogni numero è sicuramente un metodo semplice perché basta trovare il più grande. Tuttavia, ti renderai subito conto che diventa sempre più dispendioso in termini di tempo man mano che il numero di cifre aumenta.

Il metodo della scomposizione in fattori primi presenta un inconveniente simile, ma poiché possiamo raggruppare tutti i numeri primi, ad esempio in ordine crescente, possiamo introdurre un modo per elaborare un risultato un po' più velocemente.

D'altra parte, se preferisci utilizzare l'algoritmo binario o quello di Euclide per stimare qual è l'MCD di più numeri, puoi anche utilizzare un teorema che afferma che:

MCD(a, b, c) = MCD(gcf(a, b), c) = MCD(MCD(a, c), b) = MCD(MCD(b, c), a).

Ciò significa che possiamo calcolare l'MCD di due numeri qualsiasi e poi ricominciare l'algoritmo utilizzando il risultato e il terzo numero e continuare finché rimangono cifre. Non ha importanza quali due numeri scegliamo per primi.

Un altro concetto strettamente legato all'MCD è il minimo comune multiplo. Per trovare il minimo comune multiplo, utilizziamo lo stesso procedimento usato per trovare l'MCD. Una volta fatta la scomposizione in fattori primi, cerchiamo la potenza più piccola di ogni fattore, anziché la potenza più grande. Poi moltiplichiamo le potenze più alte e il risultato è il minimo comune multiplo o mcm. Questa operazione può essere eseguita a mano o con l'aiuto del calcolatore di mcm.

Il massimo comune divisore può essere stimato con l'uso dell'mcm. La seguente espressione è vera:

MCD(a, b) = |a × b| / mcm(a, b).

A causa della complessità e della durata, può essere utile trovare prima il minimo comune multiplo. Naturalmente può essere calcolato in entrambi i modi, quindi vale la pena sapere come trovare sia l'MCD che l'mcm.

Abbiamo già presentato alcune proprietà del massimo comune divisore. In questa sezione elenchiamo le più importanti:

• Se il rapporto tra due numeri interi a e b (a > b) è un intero, allora MCD(a, b) = b;

• MCD(a, 0) = a, utilizzato nell'algoritmo di Euclide;

• MCD(a, 1) = 1;

• Se a e b non hanno fattori comuni (sono coprimi), allora MCD(a, b) = 1;

• Tutti i fattori comuni di a e b sono anche divisori di MCD(a, b);

• Se b × c / a è un intero e MCD(a, b) = d, allora anche a × c / d è un intero;

• Per qualsiasi intero k: MCD(k × a, k × b) = k × MCD(a, b), utilizzato nell'algoritmo binario;

• Per qualsiasi intero positivo k: MCD(a/k, b/k) = MCD(a, b) / k;

• MCD(a, b) × mcm(a, b) = |a×b|;

• MCD(a, mcm(b, c)) = mcm(MCD(a, b), MCD(a, c)), e infine

• mcm(a, MCD(b, c)) = MCD(mcm(a, b), mcm(a, c)).

No, l'MCD di 14 e 42 non è 2. L'MCD di 14 e 42 è 14 e per trovarlo bisogna scomporre entrambi i numeri in fattori:

• I fattori di 14 sono 1, 2, 7 e 14; e
• I fattori di 42 sono 1, 2, 3, 6, 7, 14, 21 e 42.

Come puoi vedere, il numero comune più grande in entrambe le liste è 14, che è l'MCD.

L'MCD di 8 e 12 è 4. Per arrivare a questa risposta:

1. Scrivi tutti i fattori di entrambi i numeri:

   • I fattori di 8 sono 1, 2, 4 e 8, mentre
   • I fattori di 12 sono 1, 2, 3, 4, 6 e 12;

2. Elenca tutti i fattori comuni: 1, 2, 4; e

3. Il massimo comune divisore è il fattore più grande, ovvero 4.

L'MCD di 24 e 36 è 12. Possiamo arrivare a questa risposta utilizzando il metodo di Euclide:

1. Ordina i numeri in ordine crescente:

   24, 36;

2. Esegui l'operazione modulo prendendo il numero più grande come dividendo e il più piccolo come divisore:

   36 mod 24 = 12;

3. Raccogli il divisore e il resto e mettili in ordine crescente:

   12, 24;

4. Anche in questo caso, risolvi l'operazione modulo nello stesso modo:

   24 mod 12 = 0; e

5. Rimane solo un numero (il divisore, 12), quindi 12 è il massimo comune divisore.

L'MCD di 30 e 54 è 6. Possiamo utilizzare la scomposizione in fattori primi per ottenere la risposta:

1. Scrivi tutti i numeri come prodotto dei loro fattori primi:

   • 30 = 2 × 3 × 5,
   • 54 = 2 × 3 × 3 × 3;

2. Elenca tutti i fattori primi comuni: 2, 3;

3. Trova il prodotto di tutti i fattori primi comuni: 2 × 3 = 6; e

4. Il massimo comune divisore è il risultato del passo precedente. Per 30 e 54 è 6