はじめに

　$a,b$を整数として不定方程式$ax+by=1$の解の存在性について考えます. 以下の定理が知られています.

一番有名な証明は$a,2a,3a,\dots (b-1)a$をそれぞれ$b$で割った余りについて考えるやり方(フェルマーの小定理の証明などにも使えるありがちテクニック)だと思いますが, この記事では別の証明を与えます.

証明

　集合$S$を左辺が取りうる整数の集合とします. つまり$S=\{ax+by\mid x,y\in\Z\}$とします.
まず$S$の構造を調べましょう. 整数$u,v$について

$$ u(ax_1+by_1)+v(ax_2+by_2) = a(ux_1+vx_2) + b(uy_1+vy_2)$$

なので

$$ m,n \in S \Rightarrow um+vn \in S$$

です. 次に$S$の元の中で最小の自然数を$d$とします. 上の性質から任意の整数$u$について$ud\in S$です. また$S$の元で$d$の倍数でない$p$が存在すると仮定すると, 明らかに$d\neq 1$で, $p$を$d$で割り算した形, $p=qd+r$($0< r < d$)を考えれば

$$r = 1\cdot p - qd \in S$$

となりますがこれは$d$の最小性に矛盾します. つまり$S$の元はすべて$d$の倍数です.

　以上より$S=d \Z$がわかりました. 一方で明らかに$a,b\in S$で$a$と$b$は互いに素なので$d=1$に他なりません.

おわりに

　いろんな証明があると思いますが昔どっかでこの証明を読んで感動したのを覚えてます. 数年後に代数を勉強してなるほどな〜となったのも覚えています. 実際代数の言葉を用いて紹介した証明を書き直せば

• $S$は$\Z$のイデアルです.
• $\Z$は単項イデアル整域なので$S$はある$d$から生成されます.
• $S$は互いに素な元$a,b$を含んでいるので$S$は$d=1$から生成され, $S=\Z$です.

といった形になります. もっと言うと$\Z$は単項イデアル整域なのでそれゆえべズー整域でもあるということですね.