数学のブログ

整数 約数と倍数 Euclidの互除法、公約数と最大公約数

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

a と b の最大公約数をgとおく。

( a , b ) = g

このとき、 q

g | ( b - q a ) = r

すなわち、gはrの約数でもあるので、 aとrの最大公約数を

( a , r ) = g r

とおくと、

g | g r

また

、

g r | q a + r = b

すなわちbの約数でもあるので、

g r | g

よって、

g = g r

すなわち

( a , b ) = ( a , r )

である。

（証明終）