如何计算最大公约数？

更多关于最大公约数（有时也称为最大公约数） ：两个正整数 \(n_1\) 和 \(n_2\) 之间的最大公约数 (GCD) 是同时整除 \(n_1\) 和 \(n_2\) 的最大整数。通过检查通常很容易找到（即以系统的方式尝试大量数字,直到找到为止）,但这仅适用于小数字。通过检查计算大量的 GCD 可能很乏味或很困难。

幸运的是,有一种系统的,简单的（咳嗽,咳嗽）方法可以计算两个数字的 GCD。方法是这样的

• 计算 质数分解 \(n_1\) 和 \(n_2\)。象征性地,我们会有这样的东西： \[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}\]
• 在相应的素数分解中找到公共素数的列表。如果没有公共素数,那么停止,你已经发现 GCD = 1。否则,让 \(\{r_1, ..., r_k \}\) 是 \(k\) 公共素数的列表,让 \(\alpha_{i_l}, \beta_{i_l}\) 为 \(l=1,2,..,k\) 是在 \(n_1\) 和 \(n_2\) 的素数分解中找到的相应指数,对于相应的公共素数。
  
  
• GCD 计算为：\[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}\}} \]

上面的方法看起来太复杂了？？并不真地。让我们看一个例子：让我们计算 \(n_1 = 165\) 和 \(n_2 = 1575\) 的 GCD。让我们找出每个数字的素数分解（您可以使用我们的素数分解计算器）

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

由上可知：这两个数有什么共同的质数？如我们所见,公质数是 3 和 5。查看每个数字中这些公质数的指数,我们会看到两者之间的最小值。在这种情况下,3 的最小指数为 1,5 的最小指数也是 1。因此

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

除了 GDC 计算器,您还可以从我们的选择中进行选择 代数计算器和求解器 .