9.1 整除性

整除性 (divisibility) を考えると、数論の特徴がすぐに姿を現す:

定義 9.1.1

$a$ が $b$ を割り切る ($a$ divides $b$) とは、次の条件を満たす整数 $k$ が存在することを意味する:

\[ ak = b \]

$a$ が $b$ を割り切るとき $a \; | \; b$ と書く。

整除性は非常によく使われるので、整除性を意味する言葉遣いが多く存在する。次の文章は全て同じ事実を表す:

$a \; | \; b$
$a$ が $b$ を割り切る。
$a$ は $b$ の約数 (divisor) である。
$a$ は $b$ の因数 (factor) である。
$b$ は $a$ で割り切れる (divisible by $a$)。
$b$ は $a$ の倍数 (multiple of $a$) である。

定義 9.1.1 から直ちに分かる事実として、全ての $n$ で次の関係が成り立つ:

\[ n \; | \; 0, \qquad n \; | \; n, \qquad \pm 1 \; | \; n \]

また、次の関係も分かる:

\[ 0 \; | \; n \ \ \longrightarrow \ \ n = 0 \]

整除性は非常に単純だが、定義で少し遊んでみよう。古代の数秘術教団ピタゴラス学派 (Pythagorean) は、正約数の和が自身に等しい整数を完全数 (perfect number) と呼んだ。例えば $6 = 1 + 2 + 3$ と $28 = 1 + 2 + 4 + 7 + 14$ は完全数であり、$10$ $(\neq 1 + 2 + 5)$ と $12$ $(\neq 1 + 2 + 3 + 4 + 6)$ は完全数でない。Euclidユークリッドは紀元前三世紀ごろに偶数の完全数の特徴付け (問題 9.2) を与えた。では、奇数の完全数は？二千年以上が経過した現在でさえ、この疑問に対する答えを人類は手にしていない！ $10^{300}$ 以下の奇数は全て完全数でないと確かめられたものの、誰も奇数の完全数が存在しないことを証明できていない。

なんと数論に踏み込んで半ページで、人類の知識の最前線を超えてしまった。これは非常に典型的である: 数論には簡単に表明できるにもかかわらず答えるのが極めて難しい問題が溢れている。そういった問題は本章でさらにいくつか示される¹。

9.1.1 整除性に関する事実

整除性に関する基礎的な事実を次の補題にまとめる。

補題 9.1.2

$a \; | \; b$ かつ $b \; | \; c$ なら $a \; | \; c$
$a \; | \; b$ かつ $a \; | \; c$ なら、全ての $s$, $t$ に対して $a \; | \; sb + tc$
全ての $c \neq 0$ に対して $a \; | \; b \ \ \longleftrightarrow \ \ ca \; | \; cb$

証明これらの事実は定義 9.1.1 から直接従う。ここには $\text{2.}$ の証明だけを示す:

$a \; | \; b$ より、ある $k_{1} \in \mathbb{Z}$ で $ak_{1} = b$ が成り立つ。同様に $a \; | \; c$ より、ある $k_{2} \in \mathbb{Z}$ で $ak_{2} = c$ が成り立つ。ここから次を得る:

\[ sb + tc = s(k_{1}a) + t(k_{2}a) = (sk_{1} + tk_{2})a \]

よって $k_{3} ::= sk_{1} + tk_{2}$ と定めれば $sb + tc = k_{3}a$ であり、これは次の関係を意味する:

\[ a \; | \; sb + tc \]

■

$sb + tc$ の形をした整数を $b$ と $c$ の整数線形結合 (integer linear combination) と呼ぶ。本章では整数しか扱わないので、単に線形結合 (linear combination) とも呼ぶ。つまり補題 9.1.2 の $\text{2.}$ は次のように言い換えられる:

$a$ が $b$ と $c$ を割り切るなら、$a$ は $b$ と $c$ の任意の線形結合を割り切る。

線形結合は以降の議論でよく使うので、一般的な定義を示しておく:

定義 9.1.3

整数 $n$ が実数 $b_{0}$, $\ldots$, $b_{k}$ の整数線形結合 (integer linear combination) とは、次の等式を満たす整数 $s_{0}$, $\ldots$, $s_{k}$ が存在することを意味する:

\[ n = s_{0} b_{0} + s_{1} b_{1} + \cdots + s_{k} b_{k} \]

整数線形結合は線形結合 (linear combination) とも呼ぶ。

9.1.2 整除性が成り立たないとき

小学校で学んだように、ある整数で別の整数を割り切れないときでも「商」と「剰余 (余り)」は存在する。つまり:

定理 9.1.4[除算定理 (division theorem)]

$n$, $d$ が整数で、$d \neq 0$ だと仮定する。このとき次の条件を満たす二整数 $q$, $r$ が一意に定まる:

\[ n = q \cdot d + r\ \ \ \operatorname{\text{\footnotesize AND}} \ \ \ 0 \leq r < |d| \tag{9.1}\]

$q$ を「$n$ を $d$ で割った商 (quotient)」と呼び、$r$ を「$n$ を $d$ で割った剰余 (remainder)」と呼ぶ²。

本書では $n$ を $d$ で割った商を $\operatorname{qcnt}(n ,d)$ と表記し、剰余を $\operatorname{rem}(n, d)$ と表記する。

定理 9.1.4 で使われている $|d|$ は絶対値を表す。高校数学で習っていると思うが、念のため定義を示しておく:

定義 9.1.5

任意の実数 $r$ の絶対値 (absolute value) は次のように³定義される:

\[ |r| ::= \begin{cases} r & r \geq 0 \text{ のとき} \\ -r & r < 0 \text{ のとき} \end{cases} \]

定義より、$n$ と $r$ の符号にかかわらず剰余 $\operatorname{rem}(n, d)$ は非負整数である。例えば $-11 = (-2) \cdot 7 + 3$ より $\operatorname{rem}(-11, 7) = 3$ が分かる。

多くのプログラミング言語が持つ「剰余」演算は混乱の元になることがよくある。例えば、Java, C, C++ のプログラマーにとって $\texttt{32 \% 5}$ は見慣れた式だろう: 三つの言語の全てで、この式は $\operatorname{rem}(32, 5) = 2$ に評価される。一方で、$\texttt{32 \% -5}$ や $\texttt{-32 \% 5}$ といった負数が含まれる剰余演算の扱いは言語ごとに異なる。そのため、本書を読む上では自分が知っているプログラミング言語の剰余演算の振る舞いは忘れたほうがいい: 剰余は常に非負整数という数学の慣習だけを憶えておけば問題ない。

$d$ による除算の剰余は定義より $0$ から $|d| - 1$ までの整数区間に属する。こういった区間は頻繁に利用されるので、略記法を定めておくと便利である。そこで $k \leq n$ を満たす整数 $k$, $n$ に対して次のように定義する:

\[ \begin{aligned} [k .. n] &::= \left\{ i \in \mathbb{Z} \; | \; k \leq i \leq n \right\} \\ (k .. n] &::= [k, n] - \left\{ k \right\} \\ [k .. n) &::= [k, n] - \left\{ n \right\} \\ (k .. n) &::= [k, n] - \left\{ k, n \right\} \end{aligned} \]

9.1.3 容器に水を入れる問題

第 6.2.3 項では、容量が $3$ ガロンと $5$ ガロンの水を入れる容器を使って $4$ ガロンを作る問題、そして容量が $3$ ガロンと $9$ ガロンの容器を使って $4$ ガロンを作る問題を考え、異なる結論を得た。一般的には何が言えるだろうか？例えば $12$ ガロンと $18$ ガロンの容器から 4 ガロンを作れるだろうか？ $899$ ガロンと $1147$ ガロンから $32$ ガロン、あるいは $21$ ガロンと $26$ ガロンから $3$ ガロンは？

数論を使うと、この「容器に水を入れる問題」を一般的に解決できる。

容器の不変条件

容量が $a$, $b$ $\ (a \leq b)$ の容器 $1$, $2$ があるとする。この二つ容器に入った水の量を表す状態機械の遷移の例を示す:

\[ \begin{aligned} (0, 0) &\to (a, 0) && \text{容器 1 を満たす} \\ &\to (0, a) && \text{容器 2 に移す} \\ &\to (a, a) && \text{容器 1 を満たす} \\ &\to (2a - b, b) && \text{容器 2 に移す ($2a > b$ を仮定)} \\ &\to (2a - b, 0) && \text{容器 2 を空にする} \\ &\to (0, 2a - b) && \text{容器 2 に移す} \\ &\to (a, 2a - b) && \text{容器 1 を満たす} \\ &\to (3a - 2b, b) && \text{容器 2 に移す ($3a > 2b$ を仮定)} \end{aligned} \]

この例からは、それぞれの容器に入っている水の容量が常に $a$ と $b$ の線形結合であるように思える。これは遷移の回数に関する数学的帰納法を使うと簡単に証明できる:

補題 9.1.6

第 6.2.3 項で考えた問題において二つの容器の容量が $a$, $b$ のとき、それぞれの容器に入っている水の量は常に $a$ と $b$ の線形結合である。

証明遷移の回数に関する数学的帰納法で示す。帰納法の仮定 $P(n)$ を「$n$ 回の遷移の後、それぞれの容器に入っている水の量は $a$ と $b$ の線形結合である」と定める。

ベースケース: $n = 0$ のとき、二つの容器は空である。$0 \cdot a + 0 \cdot b = 0$ より $P(0)$ は成り立つ。

帰納ステップ: $n$ ステップ後の状態が $(x, y)$ で、$P(n)$ が成り立つと仮定する。つまり、それぞれの容器に入っている水の量は $x$, $y$ で、$x$, $y$ は両方とも $a$ と $b$ の線形結合だと仮定する。この上で $P(n + 1)$ を示せばよい。二つの場合を分けて考える:

$n + 1$ 回目の遷移がいずれかの容器を水で満たす、もしくはいずれかの容器の水を捨てる操作に対応するなら、その後のそれぞれの容器に入っている水の量は明らかに $a$ と $b$ の線形結合である。よって $P(n + 1)$ は成り立つ。
そうでないとき、$n + 1$ 回目の操作は一方の容器に入っている水をもう一方の容器にどちらかが満杯もしくは空になるまで操作に対応する。操作の前、水の量 $x$, $y$ は帰納法の仮定より $a$ と $b$ の線形結合である。操作の後、一方の容器は空または満杯になる。その容器に入っている水の量は $0$, $a$, $b$ のいずれかだから、もう一方の容器に入っている水の量は $x + y$, $x + y - a$, $x + y - b$ のいずれかである。これらは全て ($x$, $y$ と同様に) $a$ と $b$ の線形結合だから、$P(n + 1)$ は成り立つ。

両方の場合で $P(n + 1)$ は成り立つと示せたので、帰納ステップが完了した。 ■

これで不変条件が分かった: それぞれの容器に入っている水の量は、容器の容量の線形結合である。補題 9.1.6 からは次の系を導ける:

系

$12$ ガロンと $18$ ガロンの容器で $4$ ガロンを作ることはできない。同様に $899$ ガロンと $1147$ ガロンの容器で $32$ ガロンを作ることはできない。

証明補題 9.1.6 より、$12$ ガロンと $18$ ガロンの容器で作れる水の量は $12$ と $18$ の線形結合である。これは常に $6$ の倍数であることが補題 9.1.2 の $2.$ から分かる。つまり $4$ ガロンは作れない。同様に $899$ ガロンと $1147$ ガロンで作れる水の量は $31$ の倍数だと分かるので、$32$ ガロンも作れない。 ■

ただ、補題 9.1.2 で問題が完全に解けたとは言えない。例えば、$21$ ガロンと $26$ ガロンから $3$ ガロンを作れるかどうかは解決できない: $21$ と $26$ の正の公約数は $1$ だけであり、$1$ は当然 $3$ を割り切る。よって補題 9.1.2 からは $3$ ガロンを作れるとも作れないとも言えない。

それよりも注目してほしいのは、水の容器に関する非常に分かりやすい問題を線形結合に関する数学的な疑問に変換できた事実である。大した進歩ではないと思うかもしれない。しかし、線形結合は最大公約数という私たちがさらに慣れ親しんでいる概念と結び付いており、その事実を使うと「水の容器問題」に対する一般的な解答に近づける。

慌てないでほしい ── 本章では基本的に数論の扱いやすい部分にしか触れない。極端に難しい未解決の問題が練習問題になることはまずない。 ↩︎
この定理は「除算アルゴリズム (division algorithm)」と呼ばれる場合も多い。ただ、この主張から商と剰余を計算する方法が直ちに分かるわけではないので、本書では「除算定理」と呼ぶことにした。 ↩︎
ルートが非負の平方根を表す慣習 (問題 1.2) を利用すれば、実数 $r$ の絶対値は $\sqrt{r^{2}}$ とも定義できる。複素数に拡張された絶対値はノルム (norm) と呼ばれ、$| a + bi | ::= \sqrt{a^{2} + b^{2}} \quad (a, b \in \mathbb{R})$ と定義される。 ↩︎