仮面浪人生の日記

DAY 29 一次不定方程式、ベズーの補題

今回は一次不定方程式の諸々の定理について学んだ。

まずは次の定理について示す。

(以下の証明について、整数の集合を $\mathbb{Z}$ ,自然数の集合を $\mathbb{N}$ とかく）

定理1

ある空集合でない $\mathbb{Z}$ の部分集合 $M$ について、

$a,b\in M \Rightarrow a-b\in M\cdots (A)$ が成立するとき

$M$ に属する最小の自然数を $d$ とすると

$M=\{kd|k\in\mathbb{Z}\}$ が成立する。

証明

$M$ は空集合ではないからある要素を持ちその要素を $a\in M$ とすると

(A)より $a-a=0\in M$ である。

またこれより任意の $x\in M$ について

$0-x=-x\in M\cdots (B)$

このことから $a,b\in M$ について $a+b=a-(-b)\in M\cdots (C)$

次に、 $N=\{kd|k\in\mathbb{Z}\}$ とおくと

$N\subset M$ であることを示す。

まず、 $nd$ ( $n\in \mathbb{N}$ ) $\in M$ であることを数学的帰納法で示す。

(i) $n=1$ のときの成立は明らかである。

(ii) $n=m$ のとき成立、すなわち $md\in M$ であるとすると

$n=m+1$ のとき(C)より

$(m+1)d=d+md\in M$

よって $n=m+1$ のときも成立する。

したがって任意の自然数 $n$ について $nd\in M$

また(B)より $-nd\in M$

したがって任意の整数kについて $kd \in M$ である。

よって $N\subset M$

次に $N\supset M$ であることを示す。

$M$ の任意の要素 $x$ は整数であるから除法の原理より

$x=dq+r(0\leq r \lt d)$ となる整数 $q,r$ が存在する。

$r=x-dq$ で、 $x,dq\in M$ と(A)から $r\in M$

いま、 $r\neq 0$ を仮定すると $0\lt r \lt d$

このことは $r\in M$ であって $d$ がMに属する最小の自然数であることに反する。

したがって $r=0$

すなわち $M$ の任意の要素xは $q\in \mathbb{Z}$ を用いて $x=dq$ とかける。

したがって $N\supset M$ となって $N=M$

この定理の証明だけでもなかなか骨が折れるが、次が本陣である。

定理2

$a,b$ が $0$ でない整数であるとき、

$ax+by=1$ を満たす $x,y\in \mathbb{Z}$ が存在する $\Leftrightarrow$ $a,b$ は互いに素

証明

( $\Rightarrow$ )

$gcd(a,b)=g$ とすると $a=gA,b=gB$ とかける。

よって $gAx+gBy=g(Ax+By)=1$

$x,y$ が整数であるから $Ax+By$ も整数となり $g$ は $1$ の約数であって

このことから $g=1$

よって $a,b$ は互いに素である。

( $\Leftarrow$ )

$M=\{ax+by|x,y\in \mathbb{Z}\}$ とすると

$x,X,y,Y\in M$ について $aX+bY-(ax+by)=a(X-x)+b(Y-y)\in M$

したがって定理1より $M$ に属する最小の自然数を $d$ とすると

$M$ の要素は $d$ の倍数である。

$a=a\cdot 1 + b\cdot 0,b=a\cdot 0 +b\cdot 1$ より $a,b\in M$ だから

$a,b$ 共に $d$ の倍数である。

すなわち $d$ は $a,b$ の公約数であり、 $a,b$ が互いに素であることから $a,b$ の公約数は1のみである。

したがって $d=1$

$d=1\in M$ であるから、ある整数 $x_0,y_0$ が存在して

$ax_0+by_0=1$ となる。

よって題意は示された。

ついでにより一般的な次の定理について示す。

定理3-ベズーの補題

$a,b,c$ が $0$ でない整数であるとき、

$ax+by=c$ を満たす $x,y\in \mathbb{Z}$ が存在する $\Leftrightarrow$ $c$ は $gcd(a,b)$ の倍数

証明

$gcd(a,b)=g$ とすると、

$a=gA,b=gB$ ( $A,B$ は互いに素)とかける。

$(\Rightarrow)$

$c=ax+by=gAx+gBy=g(Ax+By)$

となり、 $Ax+By$ は整数であるから $c$ は $g$ の倍数である。

( $\Leftarrow$ )

定理2より $A,B$ が互いに素であるから

$Ax+By=1$ を満たす $x,y\in \mathbb{Z}$ が存在する。

条件より $c=gC$ とかけるから、 $Ax+By=1$ の両辺を $c=gC$ 倍して

$gACx+gBCy=c$

$aCx+bXy=c$

すなわち、 $Cx=X$ , $Cy=Y$ とおけば

$aX+bY=c$ をみたす $X,Y\in \mathbb{Z}$ が存在することがわかる。

よって題意は示された。

以上である。

これは一次方程式の分野のみならず他においても応用が効きそうな定理であるから、思いつき次第どんどん活用していきたいものだ。
いいかげん他の教科もしたいが、数学が楽しいのでなかなか他の教科に手がでない。

今日の勉強時間

新課程チャート式基礎からの数学I+A：2時間15分

合計：2時間15分