求以下兩數的最大公約數
475 和 495

已知： 475 和 495。

求解： 我們需要求出給定數字的最大公約數。


解題步驟

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

使用歐幾里得引理得到：
  • $495\ =\ 475\ \times\ 1\ +\ 20$

現在，考慮除數 475 和餘數 20，並應用除法引理得到
  • $475\ =\ 20\ \times\ 23\ +\ 15$

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

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

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

因此，495 和 475 的最大公約數是此階段的除數，即 5。


所以，475 和 495 的最大公約數是 5。

更新於： 2022年10月10日

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告