前へ / 戻る / 次へ

補助命題

　てんびんクイズの予想を式で表すと となります。そこで $ax+by$ の形の数の性質を調べることにしましょう。
証明 　$G=\{\,0\,\}$ であれば $z=0$ として Lemma が成り立ちますので、 以下、$G \neq \{\,0\,\}$ とします。

1. $G$ の $0$ でない要素 $a$ を取ります。条件より $0 = a-a \in G.$ 再び条件より $-a=0-a\in G$ となるので、$G$ は必ず正の要素を含みます。 そこで、$G$ の正の要素のうち最小のものを $z$ としましょう。
2. $z$ の倍数は全て $G$ の要素になります。なぜならば、条件を繰り返し使うことにより $2z = z + z \in G$, $3z = (2z) + z \in G$, $\cdots$ がわかり、そして 1. で示したように $0 = z-z \in G$, $(-m)z = -(mz) \in G$ ( $\forall m \in \NN$ ) となります。
3. 今度は、$G$ の全ての要素が $z$ の倍数であることを示しましょう。 $G$ の任意の要素を $x$ とし、$x$ を $z$ で割って $x = zq + r \qquad ( 0 \leqq r \lt z)$ とします。2. と条件から $r = x - zq \in G$ となりますが、もし $r \gt 0$ であれば $z$ の取り方（最小性）に矛盾しますので $r=0$ です。 すなわち $x=zq$ は $z$ の倍数になります。

以上、2° と 3° から $z$ の倍数全ての集合と $G$ が等しいことが言えました。(証明終)

$ax+by$ の形の数

証明 　$a=b=0$ のときは $G=\{\,0\,\}$, $\gcd(a,b)=0$ ですので主張が成り立ちます。 そこで、以下 $(a,b) \neq (0,0)$ とします。

1. $G$ は Th.5 の条件を満たします。なぜなら $$(ax+by) \pm (ax'+by') = a(x \pm x') + b(y \pm y').$$
2. Th.5 より $G=$ ( $z$ の倍数全ての集合 ) となる正の要素 $z$ が存在します。
3. $z \in G$ ですから $z$ 自身 $z = ax+by$ と書けます。$a$, $b$ は $\gcd(a,b)$ の倍数ですから $z$ も $\gcd(a,b)$ の倍数になります。
4. 逆に $a = a \times 1 + b \times 0$, $\quad b = a \times 0 + b \times 1$ は共に $G$ の要素ですから、$z$ の倍数になります。 つまり $z$ は $a$, $b$ の公約数ですから、Th.4 により $\gcd(a,b)$ の約数になります。

以上、3° と 4° から $z$ と $\gcd(a,b)$ が等しいことがわかります。よって 2° より $G=$ ( $\gcd(a,b)$ の倍数全ての集合 ) であることが言えました。(証明終)

前へ / 戻る / 次へ