アルゴリズム論特論(塩田)第2回 (3) $ax+by$ の形の数

補助命題

 てんびんクイズの予想を式で表すと
予想 $a$, $b$ が与えられたとき、ある $x$, $y$ が存在して $ax+by=\gcd(a,b)$ が成り立つ。
となります。そこで $ax+by$ の形の数の性質を調べることにしましょう。
Lemma 5 $\ZZ$ の、空でない部分集合 $G$ が加法と減法で閉じているとする。すなわち
$G$ の任意の要素 $a$, $b$ について $a+b \in G$ かつ $a-b \in G.$
このときある要素 $z \in G$ があって
$G=$ ( $z$ の倍数全ての集合 )
証明  $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$ の形の数

Th.6 $a$, $b$ を固定し、$ax+by$ の形の数全ての集合を
$G=\{\,ax+by\,|\,x, y \in \ZZ\,\}$
とおく。すると
$G=$ ( $\gcd(a,b)$ の倍数全ての集合 ).
証明  $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)$ の倍数全ての集合 )
であることが言えました。(証明終)
Cor.7 任意の $a, b \in \ZZ$ に対してある $x,y \in \ZZ$ が存在して
$\gcd(a,b)=ax+by$
が成り立つ。
Cor.8 てんびんクイズの答え $=\gcd(a,b)$.
Cor.9 $a$, $b\in\ZZ$ が与えられたとき、方程式
$ax+by =c$
が整数解 $(x,y)$ を持つことと、$c$ が $\gcd(a,b)$ の倍数であることが同値である。