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 .