Come calcolare il più grande divisore comune?

Ulteriori informazioni sul Greatest Common Divisor (a volte indicato anche come Greatest Common Factor) : Il massimo comune divisore (GCD) tra due numeri interi positivi \(n_1\) e \(n_2\) è il più grande intero che divide sia \(n_1\) che \(n_2\). Di solito è facile da trovare per ispezione (cioè provando molti numeri in modo sistematico, finché non lo troviamo), ma questo è vero solo per piccoli numeri. Il calcolo del GCD per grandi numeri tramite ispezione può essere noioso o semplicemente difficile.

Fortunatamente, esiste un modo semplice e sistematico (tosse, tosse) per calcolare il GCD per due numeri. Il metodo funziona così

• Calcola il file decomposizione primaria di \(n_1\) e \(n_2\). Simbolicamente, avremmo qualcosa del genere: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
• Trova l'elenco dei numeri primi comuni nella corrispondente scomposizione dei primi. Se non ci sono numeri primi comuni, allora STOP, hai scoperto che GCD = 1. Altrimenti, lascia che \(\{r_1, ..., r_k \}\) sia l'elenco dei primi comuni \(k\) e che \(\alpha_{i_l}, \beta_{i_l}\) per \(l=1,2,..,k\) gli esponenti corrispondenti trovati nella scomposizione dei primi di \(n_1\) e \(n_2\) per il comune corrispondente numeri primi.
  
  
• Il GCD viene calcolato come: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

Il metodo sopra sembra troppo complesso ?? Non proprio. Vediamo un esempio: calcoliamo il GCD per \(n_1 = 165\) e \(n_2 = 1575\). Cerchiamo di trovare la prima scomposizione di ciascuno di questi numeri (puoi usare il nostro calcolatore di scomposizione principale)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

Da quanto sopra: quali numeri primi hanno in comune questi due numeri? Come possiamo vedere, i numeri primi comuni sono 3 e 5. Guardando gli esponenti di questi numeri primi comuni in ciascuno dei numeri, guardiamo il minimo tra i due. In questo caso, l'esponente minimo per 3 è 1 e anche l'esponente minimo per 5 è 1. Pertanto

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]

Oltre al calcolatore GDC, puoi scegliere tra la nostra selezione di calcolatori e risolutori di algebra .