如何找出两个整数的最大公因数

目录方法1：使用除数算法1、去掉负号。2、了解相关3、找两个数较大的一个，作为被除数。4、写出公式?:5、大的数作为被除数，小的作为除数。6、得出商。7、得出余数，写入公式。8、再写出公式，不过用上面的除数代替这里的被除数，上面的余数作为除数。9、一直重复步骤直到余数为零。10、最后一个除数，就是最大公因数了。11、这个例子中我们找出108和30的最大公因数:12、注意第一行30和18在第二行的位置，然后除数变被除数，余数变除数，以此类推。方法2：利用素因数1、去掉负号。2、分别找出两数的素因子分解，列出来。3、找出共同4、素因子相乘，得出最大公因数。5、完成。两个数的最大公约数，也叫最大公因数，或最高公因数，是最大的能整除两个整数的数，比如20和16最大公因数是4（20和16都有更大的因数，但不是公因数了，比如8是16的因数，却不是20的因数）。学校中很多老师教的是“猜后验证”法找最大公因数，但是其实有更简单更系统的方法来准确找到最大公因数。本方法叫“欧几里德算法”。设两数为'a'、 'b'

方法1：使用除数算法

1、去掉负号。

2、了解相关词汇（32除以5）： 32 是被除数

5 是除数

6 是商

2 是余数（模数）

3、找两个数较大的一个，作为被除数。小的数作为除数。

4、写出公式?: (被除数) = (除数) * (商) + (余数)

5、大的数作为被除数，小的作为除数。

6、得出商。

7、得出余数，写入公式。

8、再写出公式，不过用上面的除数代替这里的被除数，上面的余数作为除数。

9、一直重复步骤直到余数为零。

10、最后一个除数，就是最大公因数了。

11、这个例子中我们找出108和30的最大公因数:

12、注意第一行30和18在第二行的位置，然后除数变被除数，余数变除数，以此类推。其中每一行的商都和其他的商意义不同，只隶属于这一行，对其他行没用。

方法2：利用素因数

1、去掉负号。

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 x 7

3、找出共同素因子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 x 7

4、素因子相乘，得出最大公因数。24和18的例子中，2乘以3得到6，即最大公因数。

50和35例子中，5是唯一的共同素因子，即最大公因数。

5、完成。

小提示

另一种方式来写，就是被除数mod除数= 余数。余数为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) ，我们要的不是0作为最大公因数，因此(a, b) 转换为 (b, a mod b)得到: GCD(77,91) = GCD(91,77)。 91 mod 77 得到 14 (这意味着14 是余数) ，因为不是0，就把GCD(91,77) 替换为GCD(77,14) 。 77 mod 14 得到7 也不是0，再把GCD(77,14) 换成 GCD(14,7)。 14 mod 7 得到0。因为 14 = 7 * 2 无余数，最大公因数: GCD(-77,91) = 7

若 'a' 、 'b' 都是0，则任何非零数都是他们的公因数，所以没有最大公因数。数学家一般就说最大公因数是0，这个就是本例中方法得到的。

可以用这种方法很有效地化简分数。比如上述例子，-77/91 化简为 -11/13 因为7是-77 、91的最大公因数。