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

　　在本文中：使用除数算法利用素因数
　　两个数的最大公约数，也叫最大公因数，或最高公因数，是最大的能整除两个整数的数，比如20和16最大公因数是4（20和16都有更大的因数，但不是公因数了，比如8是16的因数，却不是20的因数）。学校中很多老师教的是“猜后验证”法找最大公因数，但是其实有更简单更系统的方法来准确找到最大公因数。本方法叫“欧几里德算法”。设两数为39；a39；、39；b39；
　　方法
　　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为例：
　　242x2x2x3
　　182x3x3
　　50和35为例：
　　502x5x5
　　355x7
　　3：找出共同素因子
　　24、18为例
　　242x2x2x3
　　182x3x3
　　50和35为例
　　502x5x5
　　355x7
　　4：素因子相乘，得出最大公因数。
　　24和18的例子中，2乘以3得到6，即最大公因数。
　　50和35例子中，5是唯一的共同素因子，即最大公因数。
　　5：完成。
　　小提示
　　另一种方式来写，就是被除数mod除数余数。余数为0则GCD（最大公因数）（a，b）b，其他情况下GCD（a，b）GCD（b，amodb）
　　比如找GCD（77，91）。先用77替换77，GCD（77，91）变为GCD（77，91）。77小于91，因此换个位置。看看是否能用公式来算。下面因为77mod91得到77（因为7791x077），我们要的不是0作为最大公因数，因此（a，b）转换为（b，amodb）得到：GCD（77，91）GCD（91，77）。91mod77得到14（这意味着14是余数），因为不是0，就把GCD（91，77）替换为GCD（77，14）。77mod14得到7也不是0，再把GCD（77，14）换成GCD（14，7）。14mod7得到0。因为1472无余数，最大公因数：GCD（77，91）7
　　若39；a39；、39；b39；都是0，则任何非零数都是他们的公因数，所以没有最大公因数。数学家一般就说最大公因数是0，这个就是本例中方法得到的。
　　可以用这种方法很有效地化简分数。比如上述例子，7791化简为1113因为7是77、91的最大公因数。