整数論 — 素数・整除性・合同式

整数論は、整数を研究する分野です。素数、整除性、合同式を理解したいなら、すでに整数論の中心的な考え方を見ていることになります。

素数とは、$1$ より大きい整数で、正の約数が $1$ とその数自身のちょうど2つだけであるものです。整除性は、ある整数が別の整数を余りなく割り切るかどうかを考えます。合同式は余りを追跡する考え方で、そのためしばしば時計算とも呼ばれます。

整数論で扱うこと

この3つの考え方は互いにつながっています。

• 素数は、正の整数の基本的な構成要素です。
• 整除性は、ある整数が別の整数をちょうど割り切るかどうかを教えてくれます。
• 合同式は、整除性の問題を余りの問題として書き換えます。

たとえば、「$a$ は $n$ で割り切れる」ということは、次と同じ意味です。

$$a \equiv 0 \pmod n$$

したがって、整除性の問題はしばしば余りの問題に書き換えられます。

素数：基本となる構成要素

素数は次のように始まります。

$$2, 3, 5, 7, 11, 13, \dots$$

$2$ は唯一の偶数の素数です。ほかの偶数はすべて $2$ で割り切れるので、素数にはなれません。

$1$ より大きい正の整数が素数でないとき、その数は合成数と呼ばれます。たとえば、$21$ は

$$21 = 3 \cdot 7$$

と書けるので合成数です。

素数が重要なのは、$1$ より大きいすべての整数が、因数の順序を除けば素数の積として表せるからです。これが素因数分解の考え方です。

整除性：ある数が別の数をちょうど割り切るとき

$a$ と $b$ を整数とし、$b \ne 0$ とします。このとき「$b$ は $a$ を割り切る」とは、ある整数 $k$ が存在して

$$a = bk$$

となることを意味します。

これは次のように書きます。

$$b \mid a$$

たとえば、$20 = 4 \cdot 5$ なので $4 \mid 20$ です。しかし、$22$ を $4$ で割ると余りが出るので、$4 \nmid 22$ です。

整除性は、約数、倍数、最大公約数、最小公倍数の背景にある言葉です。また、よく知られた判定法も説明してくれます。

• ある数が $2$ で割り切れるのは、一の位が偶数のときです。
• ある数が $5$ で割り切れるのは、一の位が $0$ または $5$ のときです。
• ある数が $3$ で割り切れるのは、各桁の和が $3$ で割り切れるときです。

最後の規則は単なるコツではありません。これは合同式から出てきます。

合同式：余りを使って考える

2つの整数を $n$ で割ったときの余りが同じなら、それらは法 $n$ で合同であるといいます。これは次のように書きます。

$$a \equiv b \pmod n$$

これは、$n$ が $a-b$ を割り切ることを意味します。

たとえば、

$$17 \equiv 5 \pmod{12}$$

です。なぜなら、$17$ と $5$ はどちらも $12$ で割ると余りが $5$ になり、また $17 - 5 = 12$ を $12$ が割り切るからです。

これは便利です。なぜなら、ある数をそれと合同なもっと簡単な数に置き換えられるからです。12時間制の時計では、15時間足すことは3時間足すことと同じ効果になります。なぜなら

$$15 \equiv 3 \pmod{12}$$

だからです。

例題：なぜ $231$ は $3$ で割り切れるのか？

$231$ という数を考えます。

まず、位取りの形で書きます。

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

次に、法 $3$ で考えます。

$$10 \equiv 1 \pmod 3$$

なので、

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

が成り立ちます。

したがって、

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

となります。

$231 \equiv 0 \pmod 3$ なので、この数は $3$ で割り切れます。

これで各桁の和の規則も説明できます。10進法では、$10$ の各べきはすべて法 $3$ で $1$ と合同なので、元の数全体は各桁の和と同じ余りをもちます。

そして実際に割ると、

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

となるので、$231$ は素数ではなく合成数です。

整数論でよくある間違い

$1$ を素数だと思ってしまう

$1$ は素数ではありません。素数は正の約数をちょうど2つもたなければなりませんが、$1$ の正の約数は1つしかありません。

整除性の条件を忘れる

$b \mid a$ という表現は、$b \ne 0$ のときにだけ意味をもちます。0で割ることはできません。

等号と合同を混同する

$17 \equiv 5 \pmod{12}$ は $17 = 5$ という意味ではありません。両者の差が $12$ の倍数だという意味です。

整除判定法を使いすぎる

いくつかの判定法が手早く使えるのは、10進法ではうまく働くからです。だからといって、すべての割る数に簡単な桁の規則があるわけではありません。

整数論はどこで出てくるか

学校数学のレベルでは、整数論は因数分解、余りの問題、整除性の証明、時計のような問題に現れます。また、分数を約分するとき、共通の約数を探すとき、繰り返しの周期をもつ問題を解くときにも出てきます。

より深いレベルでは、素数と合同式は暗号理論や計算機科学でも中心的な役割を果たします。これらの考え方を使うのにその背景知識は必要ありませんが、整数論が応用の場面で何度も現れる理由を理解する助けにはなります。

自分でもやってみよう

同じ考え方を $462$ で試してみましょう。まず各桁の和を使って $3$ で割り切れるかを調べ、そのあと素数か合成数か判断できるところまで因数分解してみてください。

自分の方法を確かめたいなら、似たような整除性や余りの問題を数式ソルバーで解き、合同式の手順を自分のものと比べてみましょう。