使用歐幾里得除法演算法求 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。
廣告