約数と整数の割り算

約数

整数$a, d$に対して、ある整数$k$があって$a=kd$となるとき、$d$は$a$の約数である、または$d$は$a$を割り切るといいます。$d\ |\ a$で表します。

ここで、「ある$x$があって、$\cdots$」という表現は、「$\cdots$ を満たすような $x$ をうまく選ぶことができる」くらいの意味です。かたっくるしい言い回しですが、慣れてしまえばどうってことはありません。例を見てみましょう。

例 $\hspace{10pt}3\ |\ 9$, $-7\ |\ 21$

$3, 9$に対して、$k$として$k=3$を選ぶことで$9=k\cdot 3$にできますね。「$d$は$a$の約数である」の言い換えは「$a$を$d$で割り切ることができる」です。実際に$9$は$3$で割り切ることができて、商は$k (=3)$になると言っても同じことです。$-7, 21$についても同様です。

最大公約数

整数$a, b$の各々の約数のうち, 共通のものを公約数といいます。 公約数のうちで最大のものを最大公約数 (greatest common divisor) といって、$gcd(a, b)$ で表します。

例 $\hspace{10pt}gcd(12,16)=4$

約数というのは割り切ることのできる数のことでしたから、$12$の約数、つまり$12$を割り切ることのできる整数を並べると、

$$12, 6, 4, 3, 2, 1, -1, -2, -3, -4, -6, -12$$

ですね。おなじようにして、$16$の約数を並べてみると、

$$16, 8, 4, 2, 1, -1, -2, -4, -8, -16$$

となりますから、これらから共通する部分を取り出してみると、

$$4, 2, 1, -1, -2, -4$$

ですね。これが公約数です。

この中で一番大きな数は $4$ ですので、$12$と$16$の最大公約数は$4$です。これを $gcd(12, 16)=4$ と表します。

互いに素

ふたつの整数$a, b$が、$1, -1$以外の公約数をもたないとき、"$a, b$は互いに素である"といいます。このことは、最大公約数が$1$である、と言い換えても良いです。

つまり、

$$gcd(a, b) = 1$$

と「$a,b$は互いに素である」は同じことを言っています。

例 $4$と$9$は互いに素である。

$4$の約数は

$$-4, -2, -1, 1, 2, 4$$

で、$9$の約数は

$$-9, -3, -1, 1, 3, 9$$

ですね。共通する約数、つまり公約数は

$$-1, 1$$

だけです。なので、$4$と$9$は互いに素です。公約数が$-1, 1$だけなので、最大の公約数は$1$でしかありえないこと、つまり$gcd(4, 9) = 1$ であることも確認できるかと思います。

倍数

$k$に対して、$k\ |\ n$となる整数$n$のことを$k$の倍数といいます。ちょっとややこしいですか？「$k$の倍数とは, $k$で割り切れる数のことである」ということです。たとえば、$11$に対して、$11\ |\ 33$となるので、$33$は$11$の倍数です。

整数の集合を$\mathbb{Z}$で表しますが、$k$の倍数の集合は $k\mathbb{Z}$ と表します。

たとえば、

$$\begin{align} 2\mathbb{Z}=\{\cdots , -6, -4, -2, 0, 2, 4, 6, \cdots \} \\\ 3\mathbb{Z}=\{\cdots , -9, -6, -3, 0, 3, 6, 9, \cdots \} \end{align}$$

です。

整数の除法の一意性

約数について説明する際に、「整数$a, d$に対して、ある整数$k$があって、$n = kd$ となる」ことを「$d$は$a$の約数である、または$d$は$a$を割り切る」という...とまわりくどい言い回しをしましたが、これの別の言い回しとして、「$a$を$d$で割ってみて、あまりがでない (=「$d$は$a$を割り切る」の言い換え) ときには、$a = kd$と書ける (表せる)」と言い換えることができます。

割り切れない場合、つまり余りが$0$でない場合はどうでしょうか。

たとえば、$11$を$3$で割ると、商は$3$となり、余りは$2$となります。「余りが$2$」ということは「割り切るには$2$余分だった」ということですので、余りの$2$を割られる数の$11$から引けば$3$で割り切れるはずです。つまり、

$$\begin{align} &11 - 2 = 3 \cdot 3 \\\ \Leftrightarrow \ &11 = 3 \cdot 3 + 2 \end{align}$$

と表せます。一般に、$a$を$b$で割ったとき、商$q$と余り$r$があって、同様に考えると余り$r$を引けば割り切れる、つまり

$$\begin{align} &a - r=bq \\\ \Leftrightarrow \ &a=bq + r \end{align}$$

と表すことができます。

ところで、$11$を$3$で割る場合、商が$3$以外になることはありえず、あまりが$2$以外になることもありえませんが、これは一般に言えることでしょうか。つまり、任意に (好き勝手に) 選んだ整数 $a, b$　に対して、商$q$と余り$r$は一通りだけ存在すると言えるでしょうか。これを肯定するのが次の定理です。

定理 任意の整数 $a, b$ に対して, ある整数 $q, r$ が存在して,

$a = qb + r, 0 \le r \lt b$

となる. このような $q, r$ は、任意に選んだ $a, b$ に対してただ一つだけ存在する.

証明 まずは、うまく$q, r$を選べば、$a=qb+r$と表せることを証明します。続いて、そのような表現が一通りしか存在しないことを示します。

$a < b$のとき, $q, r$として$q = 0, r = a$を選べば, $a = qb + r$と表すことができる.

$a \ge b$のとき, $a$ がいかに大きかったとしても, 十分大きな自然数$k$をとることで, $a \lt kb$ とすることができます^{1 2}。

$a \lt kb$を満たす$k$の最小の値を$q+1$としましょう。そうすると、$k=q$ではまだ$a$以下であり、$k=q+1$で$a$より大きくなるので、

$$a \lt (q+1)b \\\ a \ge qb$$

です。すなわち $a$ は $qb$ 以上 $(q+1)b$ 未満の値であって $qb, qb+1, \cdots , qb + (b - 1)$ のいずれか³ですから、

$$a = qb + r, \hspace{10pt} 0 \le r \lt b$$

と表すことができます。

次に一意性⁴を示します。

任意⁵の $a, b$ に対して, ２通りの表し方, $a = qb + r = q^{\prime}b+r^\prime$ が可能と仮定する.

$$\begin{align} a &= qb + r \\\ a &= q^{\prime}b + r^\prime \end{align}$$

の辺々引く (左辺から左辺、右辺から右辺を引く) と、

$$\begin{align} &0 = (qb + r) - (q^{\prime} b + r^\prime ) \\\ \Leftrightarrow \ &0 = (q - q^{\prime})b + (r - r^\prime ) \\\ \Leftrightarrow \ &(q - q^{\prime})b = -(r - r^\prime ) \end{align}$$

となりますが、ここでもしも $q \ne q^\prime$ だと仮定すると、 $(q - q^\prime ) \ne 0$ となりますが、よく式を眺めてみると、$r - r^\prime$ は$b$の倍数でなければならないことに気づくかと思います。

$r - r^\prime$ は, $0 \le r, r^\prime \lt b$ であるから,

$$-b \lt r - r^\prime \lt b$$

となります⁶。 bの倍数

$$\cdots , -3b, -2b, -b, 0, b, 2b, 3b, \cdots$$

の中で

$$-b \lt r - r^\prime \lt b$$

を満たす数は $0$ だけなので、 $r - r^\prime = 0$ すなわち $r = r^\prime$ となります。しかしながら、このとき$(q - q^{\prime})b = -(r - r^\prime$ の右辺が $0$ となり かつ 左辺が $0$ とならないため$q \ne q^\prime$と仮定すると矛盾がでてくることがわかりました。

ですので、 $q = q^\prime$ です。

さらに、$q = q^\prime$ ならば

$$\begin{align} &\ qb + r = q^{\prime}b + r^\prime \\\ \Leftrightarrow &\ qb + r = qb + r^\prime \\\ \Leftrightarrow &\ r = r^\prime \end{align}$$

となりますので、結局 $q = q^\prime, r = r^\prime$ となってしまい、異なる２通りの表現 (割り算の仕方) が存在するという仮定が誤っていたことがわかります。つまり、表現はただ一つしか存在しません ■

¹. 例をひとつ挙げます。$1000 \ge 2$ ですが、 $501$ という自然数をとることによって、$1000 \lt 2 \cdot 501 = 1002$ とできます。 ↩

². アルキメデスの原理といいますが、どんなに大きな数$a$と小さな数$b$を選んできても、十分に大きな$c$を$b$と掛け合わせることで、$a \lt bc$ となる、というある意味で当たり前なことを主張しているだけです。ある意味当然といっても、数の中に無限に大きなものの存在を認める場合 (つまり無限大もまた数であると考える場合)、この主張は正しくありません。例えば、超実数では正しくありません。 ↩

³. $(q+1)b$未満の最大の整数 ($(q+1)b$より1つ小さな整数) は$(q+1)b - 1 = qb + b -1 = qb + (b-1)$ですね。 ↩

⁴. ただひとつしか存在しないこと ↩

⁵. 「任意の...に対して、...」というのは、「どんな...を選んでも、...になる」という意味です。例えば、「任意の自然数$x$に対して$x+1\gt x$」というのは、「どんな自然数を選んできてもいいです。それを$x$としましょう。このとき、$x+1 \gt x$となります」という意味です。 ↩

⁶. わかりにくければ、数直線上に$0, b$をとって, $r, r^\prime$をその区間にプロットしてると良いと思います。このとき $|r - r^\prime |$ はプロットした2点$r, r^\prime$間の距離を表していますから、$|r - r^\prime | < b$ となり、すなわち$-b < r - r^\prime < b$ であることを確認できるかと思います。 ↩

上でも述べましたが、この定理は、「どんな２つの整数を選んでも一方で他方を割ることができる」ことと、「割り算の仕方が一通りしかない (商と余りが一通りに定まる)」ことを主張していると言えます。

例 整数 $23, 9$ に対して, 整数 $2, 5$ が存在して,

$$23 = 2\cdot 9 + 5, 0 \le 5 \lt 9$$

となります。 $23$を$9$で割ったとき、商がこれ以外になることはありえませんし、余りが$5$以外になることも考えられません。