使用歐幾里得除法演算法求最大公約數
135 和 225

已知： 135 和 225。

求解： 我們需要求出這兩個數的最大公約數。


解答

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

使用歐幾里得引理得到：
  • $225\ =\ 135\ \times\ 1\ +\ 90$

現在，考慮除數 135 和餘數 90，並應用除法引理得到
  • $135\ =\ 90\ \times\ 1\ +\ 45$

現在，考慮除數 90 和餘數 45，並應用除法引理得到
  • $90\ =\ 45\ \times\ 2\ +\ 0$

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

因此，225 和 135 的最大公約數是此時階段的除數，即 45。


所以，135 和 225 的最大公約數是 45。

更新於： 2022年10月10日

瀏覽量：108 次

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.