Comment calculer le plus grand diviseur commun?

En savoir plus sur le plus grand diviseur commun (parfois également appelé le plus grand facteur commun) : Le plus grand diviseur commun (GCD) entre deux nombres entiers positifs $n_1$ et $n_2$ est le plus grand entier qui divise à la fois $n_1$ et $n_2$. Il est généralement facile à trouver par inspection (c'est-à-dire en essayant de nombreux nombres de manière systématique, jusqu'à ce que nous les trouvions), mais cela n'est vrai que pour de petits nombres. Calculer le GCD pour de grands nombres par inspection peut être fastidieux ou difficile.

Heureusement, il existe un moyen systématique et simple (toux, toux) de calculer le GCD pour deux nombres. La méthode va comme ça

• Calculez le première décomposition de $n_1$ et $n_2$. Symboliquement, nous aurions quelque chose comme ceci: $$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}$$
• Trouvez la liste des nombres premiers communs dans la décomposition principale correspondante. S'il n'y a pas de nombres premiers communs, alors STOP, vous avez trouvé que GCD = 1. Sinon, soit $\{r_1, ..., r_k \}$ la liste des nombres premiers communs $k$ et soit $\alpha_{i_l}, \beta_{i_l}$ pour $l=1,2,..,k$ les exposants correspondants trouvés dans la décomposition des nombres premiers de $n_1$ et $n_2$ pour le commun correspondant nombres premiers.
  
  
• Le GCD est calculé comme suit: $$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}\}}$$

La méthode ci-dessus semble trop complexe ?? Pas vraiment. Voyons un exemple: calculons le GCD pour $n_1 = 165$ et $n_2 = 1575$. Trouvons la décomposition première de chacun de ces nombres (vous pouvez utiliser notre calculatrice de décomposition première)

$$165 = 3 \cdot 5 \cdot 11$$ $$1575 = 3^2 \cdot 5^2 \cdot 7$$

De ce qui précède: quels nombres premiers ces deux nombres ont-ils en commun? Comme nous pouvons le voir, les nombres premiers communs sont 3 et 5. En regardant les exposants de ces nombres premiers communs dans chacun des nombres, nous regardons le minimum entre les deux. Dans ce cas, l'exposant minimum pour 3 est 1, et l'exposant minimum pour 5 est également 1. Par conséquent

$$GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15$$

Outre le calculateur GDC, vous pouvez choisir parmi notre sélection de calculateurs et solveurs d'algèbre .