使用歐幾里得除法演算法求 455 和 255 的最大公約數(HCF)。


已知

給定的數字是 455 和 255。


求解

我們必須使用歐幾里得除法演算法求給定數字 455 和 255 的最大公約數。


解法

根據歐幾里得除法引理,

$$被除數 = 除數 × 商 + 餘數$$

這裡,$455 > 255$

 

所以,用 255 除 455,

$455 = 255 × 1 + 200$

餘數 $= 200$

重複上述過程,直到餘數為 0。

現在,將 255 作為被除數,200 作為除數,

$255 = 200 × 1 + 55$

餘數 $= 55$

現在,將 200 作為被除數,55 作為除數,

 $200 = 55 × 3 + 35$

餘數 $=35$

現在,將 55 作為被除數,35 作為除數,

 $55 = 35 × 1 + 20$

餘數 $=20$

現在,將 35 作為被除數,20 作為除數,

 $35 = 20 × 1 + 15$

餘數 $=15$

現在,將 20 作為被除數,15 作為除數,

 $20 = 15 × 1 + 5$

餘數 $=5$

現在,將 15 作為被除數,5 作為除數,

 $15 = 5 × 3 + 0$

餘數 $=0$

因此,455 和 255 的最大公約數是 5。



更新於: 2022-10-10

78 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告