数学のブログ

整数 約数と倍数 Euclidの互除法により最大公約数を求める

親切な代数学演習 新装2版―整数・群・環・体 (加藤 明史(著)、現代数学社)の第Ⅰ部(整数)、第1章(約数と倍数)の問15の解答を求めてみる。

15-1

105 = 38 · 2 + 29 38 = 29 · 1 + 9 29 = 9 · 3 + 2 9 = 2 · 4 + 1 2 = 1 · 2 + 0

よって、最大公約数は1。

( 38 , 105 ) = 1

15-2

11557 = 7553 · 1 + 4004 7553 = 4004 · 1 + 3549 4004 = 3549 · 1 + 455 3549 = 455 · 7 + 364 455 = 364 · 1 + 91 364 = 91 · 4

よって、最大公約数は91。