141203 初版 141203 更新

ユークリッドの互除法 実行例

数学の小部屋  > 例題のない教科書   > 整数  

a = 2014 と b = 250 の最大公約数を互除法で求めてみる。

n a b q r
1 2014 250 ① 8 14 ②
2 250 ① 14 ② 17 12 ③
3 14 ② 12 ③ 1 2 ④
4 12 ③ 2 ④ 6 0
機械的に r = 0 まで書いてみたが
n = 3 まででよいし，
気づいた時点で(例えば n = 2)やめてもよい。
あくまで，求めるための手段なのだから。