次: 部屋割り論法 上: 一次不定方程式 前: 不定方程式の整数解

差で閉じた部分集合

一つの方法のための準備が次の定理である．

定理 6        整数からなる空でなく$\{0\}$でもない集合$A$が次の条件を満たす．

$$a,\ b\in A\quad \Rightarrow \quad a-b\in A$$

このとき集合$A$はある整数$d$の倍数の全体と一致する．

集合$A$は差をとる演算に関して閉じている． 整数からなる集合$A$が差で閉じていれば， ある整数$d$が存在して

$$A=\{\ dn\ \vert\ n :整数 \}$$

と表されるということを意味している．

証明      条件から$0=a-a\in A$である． その結果，$a\in A$なら $-a=0-a\in A$である． また，自然数$n$に対して$na\in A$のとき

$$(n+1)a=na-(-a)\in A$$

となるので，数学的帰納法によって$a\in A$なら$na\in A$である． このとき$-na \in A$でもあるので，整数$n$に対して$na\in A$である．

$A$の要素のうち正の要素からなる部分集合をとる．自然数の部分集合なので最小要素が存在する．それを$d$とする．$A$の任意の要素$a$をとり$d$で割る．

$$a=dq+r\quad 0\le r <d$$

とおく．$d\in A$より$dq \in A$である．よって $r=a-dq \in A$である． ここでもし$r>0$なら$d$が正で最小の要素であることに反する． よって$r=0$，つまり$A$の任意の要素$a$は$d$の倍数である． つまり $A\subset\{\ dn\ \vert\ n :整数 \}$である．

逆に$d\in A$なので，最初に示したように整数$n$に対して$nd \in A$． つまり， $A\supset \{\ dn\ \vert\ n :整数 \}$も成り立つ．よって $A=\{\ dn\ \vert\ n :整数 \}$が示された． (証明終わり)

この定理の証明では，自然数の部分集合には最小の要素が存在することと除法の定理がもっともカギとなるところで用いられている．

1次不定方程式の解の存在

以上の準備のもと，次のことが示される．

定理 7        整数係数の方程式$ax+by=1$について次のことが成り立つ．

(1)

整数解が存在すれば$a$と$b$は互いに素である．

(2)

$a$と$b$が互いに素なら整数解が存在する．

証明

(1)を示す． 整数解を$m,\ n$，$a$と$b$の最大公約数を$d$とし，$a=da',\ b=db'$とおく．

$$am+bn=d(a'm+b'n)=1$$

$d$が1の約数となり$d=1$．つまり$a$と$b$は互いに素である．

(2)を示す． 集合$A$を $A=\{\ px+qy \ \vert\ x,\ y\in \mathbb{Z}\ \}$ とおく． $a=px_1+qy_1$，$b=px_2+qy_2$が$A$に属せば

$$a-b=p(x_1-x_2)+q(y_1-y_2)\in A$$

である．したがって$A$は整数の差で閉じた集合である. その結果定理6によって$A$は$A$に属するある整数$d$の倍数の全体となる． この$d$は$A$の要素なので$d=px_0+qy_0$と表される．

$$\begin{eqnarray*} &&p=p\cdot 1+q\cdot 0 \in A,\ \\ &&q=p\cdot 0+q\cdot 1 \in A \end{eqnarray*}$$

なので$p$も$q$も$d$の倍数である． つまり$d$は$p$と$q$の公約数である． $p$と$q$は互いに素なので$d=1$である． よって方程式$px+qy=1$には解$(x_0,\ y_0)$が存在した． (証明終わり)