找出以下數字對的最大公約數
70 和 30

已知： 70 和 30。

求： 此處我們需找出給定數字的最大公約數。



解法

使用歐幾里德除法演算法求最大公約數

使用歐幾里德引理得： 

  • $70\ =\ 30\ \times\ 2\ +\ 10$

現在，考慮除數為 30 和餘數為 10，並應用除法引理可得

  • $30\ =\ 10\ \times\ 3\ +\ 0$

餘數已變為零，我們無法繼續進行。 

因此，70 和 30 的最大公約數是此階段的除數，即 10。

所以，70 和 30 的最大公約數是 10。

更新於： 2022-10-10

101 檢視次數

職業起航

完成課程獲取認證

開始學習
廣告