如何找出兩個整數的最大公因數

目錄方法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的最大公因數。