• 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
• 件名は「アルゴリズム論特論第２回出席」とでもしてください。
• 内容は何でもいいです。

記号

• この講義では、全ての整数から成る集合を $\ZZ$、すべての自然数から成る集合を $\NN$ と表すことにします。 $\NN$ には $0$ は入れないことにします。 N は natural number の N で、Z はドイツ語の ganze Zahl の Z です。
• 今日は小文字のアルファベット $a$, $b$, $c$, $\cdots$ は全て整数を表すとします。

今日のテーマ

最大公約数と $ax+by$ の形の数

てんびんクイズ

　まず、次のクイズをやってみましょう。

• $a=3$, $b=5$ のときは？
  
  答え
  答え  左の皿に 3 グラムの分銅を 2 個、右の皿に 5 グラムの分銅を 1 個乗せると、その差として 1 グラムを測れる。$3 \times 2 - 5 \times 1 = 1$
• $a=5$, $b=7$ のときは？
  
  答え
  答え  左の皿に 5 グラムの分銅を 3 個、右の皿に 7 グラムの分銅を 2 個乗せると、その差として 1 グラムを測れる。$5 \times 3 - 7 \times 2 = 1$
• $a=17$, $b=23$ のときは？
  
  答え
  答え  左の皿に 17 グラムの分銅を 4 個、右の皿に 23 グラムの分銅を 3 個乗せると、その差として 1 グラムを測れる。$17 \times (-4) + 23 \times 3 = 1$
• $a=6$, $b=10$ のときは？
  
  答え
  答え  これは 1 問目の 2 倍の重さなので、左の皿に 6 グラムの分銅を 2 個、右の皿に 10 グラムの分銅を 1 個乗せると、その差として 2 グラムを測れる。$6 \times 2 - 10 \times 1 = 2$

　どうやらこんな予想ができそうです：

最大公約数 gcd と最小公倍数 lcm

　まずは $0$ についての注意から。 $0$ との整除関係は日頃あまり意識しませんが、このように考えます。次は記号の定義 ただし

• $\gcd(a, b)$ は必ず 0 以上に定めます。
• 片方が 0 のときは $\gcd(a, 0)=|\,a\,|$ となります。( Rem.2 より $|\,a\,|$ も $0$ の約数ゆえ。)
• 両方が 0 のときは $\gcd(0, 0)=0$ と定めます。
  ( Rem.1 から任意の整数が $0$ の約数なので、$\infty$ となりそうに思いますが、こう約束すると後述の Th.6 が例外なく成立します。)
• $\mbox{lcm}$ も両方が 0 のときは $\mbox{lcm}(0, 0)=0$ と定めます。

また、それぞれ何の略かと言うと

• gcd = greatest common divisor
• lcm = least common multiple

です。 ※　最大公約数・最小公倍数は、公約数や公倍数の中の大小関係で定義しますが、次のように、 他の公約数・公倍数との間に整除関係を持つのが面白いところです。
証明　$x$ を $a$, $b$ の任意の公倍数、$c=\mbox{lcm}(a,b)$ とします。 $x$ を $c$ で割って $x = cq+r \qquad ( 0 \leqq r \lt c)$ とすると、 $r = x -cq$ であり、$x$ も $c$ も $a$, $b$ の公倍数ですから、$r$ も $a$, $b$ の公倍数となります。 もし $r \gt 0$ なら $c$ が最小の公倍数であることに反しますから $r=0$. よって $x=cq$ は $c$ の倍数になります。(証明終)
証明　$x$ を $a$, $b$ の任意の公約数とし、 $d=\gcd(a,b)$, $y=\mbox{lcm}(x,d)$ とします。

$x$ も $d$ も $a$, $b$ の公約数

   $\Rightarrow$  $a$ も $b$ も $x$, $d$ の公倍数

   $\Rightarrow$  $a$ も $b$ も $y$ の倍数　( Th.3 より )

   $\Rightarrow$  $y$ は $a$, $b$ の公約数

   $\Rightarrow$  $y \leqq d$

他方、$y=\mbox{lcm}(x,d)$ は $d$ の倍数ですから $y \geqq d$ です。 $y \leqq d$ かつ $y \geqq d$ から $y=d$ となり、 すると $d=\mbox{lcm}(x,d)$ が成り立つので $x$ は $d$ の約数となります。 (証明終)

$ax+by$ の形の数

　てんびんクイズの予想を式で表すと となります。そこで $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$ が等しいことが言えました。(証明終)
証明 　$a=b=0$ のときは $G=\{\,0\,\}$, $\gcd(a,b)=0$ ですので Th. は成り立ちます。 そこで、以下 $(a,b) \neq (0,0)$ とします。

1. $(ax+by) \pm (ax'+by') = a(x \pm x') + b(y \pm y')$ ですから $G$ は La'5 の条件を満たします。 従って $G=$ ( $z$ の倍数全ての集合 ) となる正の要素 $z$ が存在します。
2. $z \in G$ ですから $z$ 自身 $z = ax+by$ と書けます。$a$, $b$ は $\gcd(a,b)$ の倍数ですから $z$ も $\gcd(a,b)$ の倍数になります。
3. 逆に $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)$ の約数になります。

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

互いに素

「どちらも素数」という意味ではありません。恥ずかしいので間違えないように。
証明　Th.11 より $ax+by=1$ を満たす $x$, $y$ を取ると $c = 1 \times c = (ax+by)c = a(cx) + (bc)y$ となり、$bc$ が $a$ の倍数ゆえ右辺は $a$ の倍数です。(証明終)

※　$\gcd$ や、Th.11 の $x$ が、RSA 暗号をはじめとする公開鍵暗号の設計でとても重要になります。

まとめ

• 2つの整数 $a$, $b$ に対して次の2つの集合は一致する：
  • $a x + b y$ ( $x$, $y$ は整数 ) の形で書ける整数全体の集合
  • $\gcd(a, b)$ の倍数全体の集合
• 特に、$a$, $b$ を与えたとき、$a x + b y = \gcd(a, b)$ を満たす $x$, $y$ が必ず存在する。
• $a$, $b$ が互いに素ならば $a x + b y = 1$ を満たす $x$, $y$ が必ず存在する。

自宅学習の例

• $a=7^5=16807$ と $b=11^4 = 14641$ に対して $ax+by=$ を満たす整数 $x$, $y$ をひと組みつけてみましょう。