数学のブログ

整数 1次合同式 1次不定方程式、整数かいが存在するための必要十分条件、係数、最大公約数、倍数

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

a と b の最大公約数をgとする。

( a , b ) = g

また、

a = a 0 g b = b 0 g

とおく。

このとき、

a x + b y = c a 0 g x + b 0 g y = c ( a 0 x + b 0 y ) g = c

である。

a x + b y = c

に整数解x、 y が存在するとき、左辺はgで割り切れるので、 右辺もgの倍数で、

c = c 0 g = c 0 ( a , b )

である。

逆に、

( a , b ) = g | c

となる。

( a 0 , b 0 ) = 1

なので、

a 0 x 0 + b 0 y 0 = 1

を満たす

x 0 , y 0 ∈ ℤ

が存在する。

よって、

( a 0 x 0 + b 0 y 0 ) c 0 g = c 0 g ( a 0 g ) ( x 0 c 0 ) + ( b 0 g ) ( y 0 c 0 ) = c a ( x 0 c 0 ) + b ( y 0 c 0 ) = c

ゆえに、

a x + b y = c

に整数解が存在する。