ユークリッドの互除法公約数を求める

互除法を用いて最大公約数を求める問題です。

大きい2つの整数の最大公約数を求める場合はユークリッドの互除法の利用が有効です。

プリント内の問題の解答を示しておきますのでプリント内でやり方を確認後、練習問題に取り組んでみてください。

練習問題①

988＝817・1＋171
817＝171・4＋133
171＝133・1＋38
133＝38・3＋19
38＝19・2＋０　　よって答えは19となる

練習問題②

1201＝997・1＋204
997＝204・4＋181
204＝181・1＋23
181＝23・7＋20
23＝20・1＋3
20＝3・6＋2
3＝2・1＋1
2＝1・2＋０　　よって答えは1となる

練習問題③

966＝667・1＋299
667＝299・2＋69
299＝69・4＋23
69＝23・3＋０　よって答えは23となる

練習問題④

8177＝3315・2＋1547
3315＝1547・2＋221
1547＝221・7＋0　よって答えは221となる

ユークリッド互除法公約数プリントはこちら