内容

• 脚步
• 方法 1 of 2：除法算法
• 方法 2 of 2：素因数
• 提示

两个整数的最大公约数 (GCD) 是除以这些数字中的每一个的最大整数。例如，20和16的gcd是4（16和20都有很大的约数，但它们并不常见——例如，8是16的约数，但不是20的约数）。有一种简单而系统的寻找 GCD 的方法，称为“欧几里得算法”。本文将向您展示如何找到两个整数的最大公约数。

脚步

方法 1 of 2：除法算法

1. 1 省略任何减号。
2. 2 学习术语： 当 32 除以 5 时，
   • 32 - 股息
   • 5 - 除数
   • 6 - 私人
   • 2 - 余数
3. 3 确定较大的数字。 它将是可整除的，较小的数字将是除数。
4. 4 写出以下算法： (股息) = (除数) * (商) + (余数)
5. 5 在被除数位置放一个较大的数，在除数位置放一个较小的数。
6. 6 找出较大数除以较小数的次数，并写出结果而不是商。
7. 7 找出余数并将其写在算法中的适当位置。
8. 8 再次编写算法，但 (A) 将前一个除数写为新的被除数，并且 (B) 将前一个余数写为新的除数。
9. 9 重复上一步直到余数为0。
10. 10 最后一个除数将是最大公约数 (GCD)。
11. 11 例如，让我们找出 108 和 30 的 GCD：
12. 12 注意第一行中的数字 30 和 18 如何形成第二行。 然后18和12形成第三行，12和6形成第四行。不使用 3、1、1 和 2 的倍数。它们表示除数可被除数整除的次数，因此每行都是唯一的。

方法 2 of 2：素因数

1. 1 省略任何减号。
2. 2 找出数的质因数。 如图所示展示它们。
   • 例如，对于 24 和 18：
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • 例如，对于 50 和 35：
     • 50- 2 x 5 x 5
     • 35- 5 × 7
3. 3 找出共同的质因数。
   • 例如，对于 24 和 18：
     • 24- 2 × 2 × 2 × 3
     • 18- 2 X 3 × 3
   • 例如，对于 50 和 35：
     • 50 - 2 x 5 × 5
     • 35- 5 × 7
4. 4 乘以公因数。
   • 对于 24 和 18，乘以 2 和 3 并得到 6... 6是24和18的最大公分母。
   • 没有什么可以乘以 50 和 35。 5 是唯一的公因数，就是GCD。
5. 5 制成！

提示

• 一种写法是：股息> 模除法器> = 余数；如果 mod b = 0，则 GCD (a, b) = b，否则 gcd (a, b) = gcd (b, a mod b)。
• 例如，让我们找到 GCD (-77.91)。首先，使用 77 而不是 -77：GCD (-77.91) 转换为 GCD (77.91)。 77 小于 91，所以我们必须交换它们，但如果我们不交换，请考虑算法如何工作。当计算 77 mod 91 时，我们得到 77 (77 = 91 x 0 + 77)。由于这不为零，我们考虑情况(b, a mod b)，即GCD (77.91) = GCD (91.77)。 91 mod 77 = 14（14 是余数）。它不为零，因此 GCD (91.77) 变为 GCD (77.14)。 77 mod 14 = 7。这不是零，所以 GCD (77.14) 变成 GCD (14.7)。 14 mod 7 = 0（因为 14/7 = 2 没有余数）。答案：GCD (-77.91) = 7。
• 所描述的方法对于简化分数非常有用。在上面的例子中：-77/91 = -11/13，因为 7 是 -77 和 91 的最大公分母。
• 如果 a 和 b 等于 0，则任何非零数都是它们的除数，因此在这种情况下不存在 GCD（数学家简单地认为 0 和 0 的最大公约数是 0）。