整数

home > 数学の基礎

数は数学の基礎であり、数系をより深く理解するためにまず最も単純な基礎に立ち返る必要がある。この基礎こそが自然数である。自然数が数学において演じる基礎的な役割は、Kronecker（クロネッカー，1823--1891）に次のような感慨を抱かせた。「神が自然数を創り、その他はすべて人間の仕事である」。

正整数と整数

前と同じ記号を用い、正整数（0 を含まない自然数）の集合を

$$\mathbb{N} = \{1,\, 2,\, 3,\, \cdots\}$$

と記す。この集合には最も基本的な算術があり、算術の基礎は正整数の加法と乗法がいくつかの規則に従っていることにある。私たちが普遍的な性質として興味を持つのがまさにこれらの規則であり、加法と乗法の演算規則をまとめると次のとおりである。

加法演算： 任意の $a, b \in \mathbb{N}$ に対して、唯一確定した正整数が存在し、これを $a$ と $b$ の和と呼び、$a + b$ と記す。加法演算は次の規則を満たす。

交換律 $a + b = b + a$.
結合律 $(a + b) + c = a + (b + c)$.

乗法演算： 任意の $a, b \in \mathbb{N}$ に対して、唯一確定した正整数が存在し、これを $a$ と $b$ の積と呼び、$a \cdot b$ または $ab$ と記す。乗法演算は次の規則を満たす。

交換律 $ab = ba$.
結合律 $(ab)c = a(bc)$.
分配律 $a(b + c) = ab + ac$.
単位元 $1 \cdot a = a \cdot 1 = a$.

順序関係： 任意の $a, b \in \mathbb{N}$ に対して、$c \in \mathbb{N}$ が存在して $a = b + c$ となるとき、$a > b$ または $b < a$ と記す。任意の二つの数 $a$ と $b$ について、次の三つの関係のうちちょうど一つが成立することが証明できる。

$a < b,\quad a = b,\quad a > b$.

順序関係はさらに次を満たす。

$a < b$ かつ $b < c$ ならば $a < c$.
$a < b$ ならば任意の $c \in \mathbb{N}$ に対して $a + c < b + c$ が成立する。
$a < b$ ならば任意の $c \in \mathbb{N}$ に対して $ac < bc$ が成立する。

正整数において最も重要で本質的な性質は帰納公理であり、この公理から出発して最小数原理と数学的帰納法を論じることができる。補足として、最小数原理のほかに最大数原理も得られる。完全性のためにそれらをまとめて列挙する。

帰納公理 $S \subseteq \mathbb{N}$ とする。$S$ が次の条件 (a) $1 \in S$、(b) $n \in S$ ならば $n + 1 \in S$ を満たすならば、$S = \mathbb{N}$ である。

定理1（最小数原理） $S$ を $\mathbb{N}$ の空でない部分集合とする。$S$ には最小の正整数が存在する。

定理2（最大数原理） $S$ を $\mathbb{N}$ の空でない部分集合とする。$S$ が上界を持つとは、正整数 $m$ が存在して任意の $s \in S$ に対して $s \leqslant m$ となることをいう。$S$ が上界を持てば、$S$ には最大の正整数が存在する。すなわち $s_0 \in S$ が存在して任意の $s \in S$ に対して $s \leqslant s_0$ となる。

次に正整数を整数に拡張する。一つは「0」を導入し、もう一つは負の整数 $-a$（$a \in \mathbb{N}$）を導入する。こうして整数の集合は

$$\mathbb{Z} = \{0, \pm 1, \pm 2, \pm 3, \cdots\}.$$

整数 $\mathbb{Z}$ には加法が定義でき、加法演算規則 (1)、(2) が適用でき、かつ $0$ は

$$0 + a = a + 0 = a, \quad a \in \mathbb{Z}$$

を満たす。さらに各 $a \in \mathbb{Z}$ に対して唯一の $x \in \mathbb{Z}$ が存在して

$$a + x = 0$$

となる。この $x$ を $-a$ と記す。こうして任意の $a, b \in \mathbb{Z}$ に対して方程式

$$a + x = b$$

は $\mathbb{Z}$ 中に唯一の解 $x = b - a$ を持つ。こうして $\mathbb{Z}$ において加法の逆演算、すなわち減法を行うことができる。代数学では加法と減法が可能であり上述の演算規則を満たす集合を加法群という。したがって $\mathbb{Z}$ は加法群である。

整数 $\mathbb{Z}$ の乗法は演算規則 (3)、(4)、(5)、(6) を満たす。加法・減法も乗法も可能な集合を（交換）環という。乗法について

$$0 \cdot a = 0 \quad (a \in \mathbb{Z}), \qquad ab = 0 \iff a = 0 \text{ または } b = 0.$$

このような性質を持つ環を零因子なし環という。したがって $\mathbb{Z}$ は零因子なし環であり、乗法の消去律が成立する。すなわち任意の $b \neq 0$ に対して

$$ab = cb \Rightarrow a = c.$$

整数 $\mathbb{Z}$ にも順序の概念があり、規則 (7)、(8)、(9) を満たす。ただし規則 (10) には条件 $c > 0$ を加える必要があり、

$a < b$ ならば $c > 0$ のとき $ac < bc$.

正整数集合 $\mathbb{N}$ の他の性質も同様にある。

例1.1 整数集合 $\mathbb{Z}$ の空でない部分集合 $E$ について、$E$ が下界（または上界）を持つとき、すなわちある $m \in \mathbb{Z}$ が存在して任意の $n \in E$ に対して $n \geqslant m$（または $n \leqslant m$）となるとき、$E$ は最小（または最大）の整数を持たなければならない。

証明

$E$ の下界を $l \in \mathbb{Z}$ とする。任意の $n \in E$ に対して $n - l + 1 > 0$ であり、$E' = \{n - l + 1 \mid n \in E\} \subset \mathbb{N}$ は正整数の空でない部分集合であるから最小数 $m > 0$ を持つ。こうして $n = m + l - 1$ が $E$ の最小数となる。

整数 $\mathbb{Z}$ においてはさらに絶対値が定義できる：

$$|a| = \begin{cases} a, & a \in \mathbb{N} \\ 0, & a = 0 \\ -a, & -a \in \mathbb{N} \end{cases}$$

したがって $|a|$ は非負の整数である。絶対値は次の性質を持つ。

$|ab| = |a||b|$.
（三角不等式） $|a + b| \leqslant |a| + |b|$.

以上が正整数集合 $\mathbb{N}$ と整数集合 $\mathbb{Z}$ に関するいくつかの基本的な事項である。

整数の整除性

前述の議論において、整数集合 $\mathbb{Z}$ は加法・乗法・減法が可能である。しかし一般には除法は行えない。すなわち二つの整数 $a, b$（$b \neq 0$）に対して $\dfrac{a}{b}$ は必ずしも整数であるとは限らない。あるいは $a = bc$ となる整数 $c$ が必ず存在するとは限らない。ここから整数の最初の基本概念である整数の整除性が導き出される。

定義3 $a, b$ を二つの整数、$b \neq 0$ とする。もし $a = bc$ となる整数 $c$ が存在するならば、$b$ は $a$ を整除するといい、$b \mid a$ と記す。$b$ は $a$ の約数（または因数）と呼ばれ、$a$ は $b$ の倍数と呼ばれる。そのような整数 $c$ が存在しないならば、$b$ は $a$ を整除しないといい、$b \nmid a$ と記す。

整除の上記の定義から、次の基本的な性質が直ちに導かれる。

定理4 $a, b, c$ を整数とする。

$b \mid a$ かつ $c \neq 0$ ならば $bc \mid ac$ であり、逆も成り立つ。特に $b \mid a$ は $(\pm b) \mid (\pm a)$ と同値である。
$b \mid c$ かつ $c \mid a$ ならば $b \mid a$.
$b \mid a$ かつ $b \mid c$ ならば $b \mid (xa + yc)$（$x, y \in \mathbb{Z}$）。
$b \mid a$ かつ $a \neq 0$ ならば $|b| \leqslant |a|$。したがって $b \mid a$ かつ $a \mid b$ ならば $|a| = |b|$。

この定理から次の二つの定理が得られる。

定理5（整数の除法） $a, b$ を整数、$b \neq 0$ とする。このとき唯一の整数の組 $q, r$ が存在して

$$a = bq + r, \quad 0 \leqslant r < |b|$$

を満たす。整数 $q$ を $a$ を $b$ で割った商、$r$ を $a$ を $b$ で割った余りという。明らかに $b \mid a$ となるのは $r = 0$ のとき、すなわち $q = \dfrac{a}{b}$ が整数となるときに限る。

証明

$b \nmid a$ と仮定して

$$E = \{a - bk \mid k \in \mathbb{Z}\}$$

と定める。$k = -nb$ ととれば $a - bk = a + nb^2$ となり、$n$ が十分大きい正整数ならば $a - bk > 0$、すなわち $E$ には正整数が含まれる。最小数原理より $E \cap \mathbb{N}$ には最小数が存在し、$E$ には最小の正整数が存在する。それを

$$r = a - bq > 0, \quad q \in \mathbb{Z}$$

とする。明らかに $r \neq |b|$。なぜなら $a = b(q \pm 1)$ となれば $b \mid a$ に矛盾するからである。

$r > |b|$ と仮定すると、$r' = r - |b| > 0$ となり、$r' = r - (\pm b) = a - b(q \pm 1) \in E$ であり、しかも $r > r' > 0$ となって $r$ が $E$ の最小正整数であることに矛盾する。したがって $r < |b|$。

一意性を証明するために、もう一組の整数 $q_1, r_1$ が定理の条件を満たすとすると

$$a = bq_1 + r_1, \quad 0 \leqslant r_1 < |b|$$

となる。すると

$$b(q - q_1) + (r - r_1) = 0$$

から $b \mid (r - r_1)$ が導かれる。しかし $0 \leqslant |r - r_1| < |b|$ であるから $r - r_1 = 0$、したがって $q - q_1 = 0$。

この定理の最も単純な例は $b = 2$ の場合であり、整数を 2 で割った余りには 0 か 1 の二通りしかない。余りが 0（すなわち 2 で割り切れる）の整数が偶数、余りが 1 の整数が奇数であり、偶数と奇数の一般的な表示は

$$2k, \quad 2k + 1, \quad k \in \mathbb{Z}$$

である。

同様に 3 で整数を割ることを考えると、余りは 0、1、2 の三通りしかない。したがって 3 で割った整数は三つの類に分かれ、それぞれ

$$3k;\quad 3k+1;\quad 3k+2, \quad k \in \mathbb{Z}.$$

整数の整除性からもう一つの重要な概念が導かれる。

定義6 $a,\,b$ を少なくとも一方は零でない整数とする。整数 $d$ が次を満たすとき、

$d$ は $a$ と $b$ の公約数（共通の約数）である。すなわち $d\mid a$、$d\mid b$。
$d$ は $a$ と $b$ の公約数の中で最大のものである。すなわち他の公約数 $d'$ があれば $d' \leqslant d$。

$d$ を $a,\,b$ の最大公約数という。

$d$ が $a$ と $b$ の公約数ならば $-d$ も公約数であるから、最大公約数は必ず正整数である。二つの数 $a$ と $b$ の最大公約数を

$$d = (a,\,b)$$

と記す。

例えば $(4,6)=2$、$(6,9)=3$、$(10,9)=1$。

特に、二つの整数 $a$ と $b$ の最大公約数 $(a,b)=1$ のとき、$a$ と $b$ は互いに素であるという。

ここでは二つの数の最大公約数の問題のみを考えるが、二つ以上の数の組の最大公約数は

$$d = (a_1,\,a_2,\,\cdots,\,a_n)$$

と記し、$d$ が $a_1,\,a_2,\,\cdots,\,a_n$ の最大公約数であることを表す。

特に $(a_1,\,a_2,\,\cdots,\,a_n)=1$ のとき、数の組 $a_1,\,a_2,\,\cdots,\,a_n$ は互いに素であるという。

数の組 $a_1,\,a_2,\,\cdots,\,a_n$ の任意の二つの数が互いに素である（$(a_i,\,a_j)=1$、$i\neq j$）とき、数の組は二つずつ互いに素であるという。

明らかに、二つずつ互いに素な数の組は互いに素である。しかし互いに素な数の組が二つずつ互いに素であるとは限らない。例えば $(2,3,4)=1$ であるが、その中の 2 と 4 は互いに素でない。

ユークリッドの互除法

二つの数の最大公約数を求める問題を考えよう。この問題を解くためにまず、整数の除法に基づく次の補題を示す。

補題7 任意の二つの整数 $a$ と $b$ に対して、整数の除法によれば

$$a = bq + r$$

となる。このとき

$$(a,\,b) = (b,\,r).$$

すなわち $a$ と $b$ の最大公約数は、$a$ を $b$ で割った余り $r$ と $b$ の最大公約数に等しい。

これはある数 $u$ が $a$ と $b$ の公約数であれば、整数 $s,\,t$ が存在して $a = su,\, b = tu$ となるので、$u$ は $r = a - bq = su - tuq = (s-tq)u$ をも整除できる。したがって $a$ と $b$ の任意の公約数は $b$ と $r$ の公約数でもあり、逆も成り立つ。よって $a,\,b$ と $b,\,r$ の公約数は同じであり、当然 $(a,b) = (b,r)$ となる。特に $r=0$（$b\mid a$）のとき、明らかに $(a,b)=(b,0)=b$ となる。

次に有名な Euclid（紀元前 330 年頃〜紀元前 275 年頃）の互除法を述べる。

任意の二つの整数 $a$ と $b$ に対して、$b > 0$ として差し支えなく、整数の除法を繰り返し適用する：

$$\begin{aligned}a &= bq_0 + r_0, & &0 < r_0 < b, \\ b &= r_0 q_1 + r_1, & &0 < r_1 < r_0, \\ r_0 &= r_1 q_2 + r_2, & &0 < r_2 < r_1, \\ r_1 &= r_2 q_3 + r_3, & &0 < r_3 < r_2, \\ &\quad\vdots & &\quad\vdots \\ r_{n-2} &= r_{n-1}q_n + r_n, & &0 < r_n < r_{n-1}, \\ r_{n-1} &= r_n q_{n+1} + 0.\end{aligned}$$

余り $r_1,\,r_2,\,\cdots$ が 0 にならない限りこれを続ける。なぜなら

$$b > r_1 > r_2 > r_3 > \cdots > 0$$

であってすべての余りは正整数なので、この互除の過程は無限に続くことはなく、最多で $n \leqslant b$ 歩で終了し、$r_{n-1} = r_n q_{n+1} + 0$ となる。

補題7 を繰り返し用いると

$$(a,\,b) = (b,\,r_0) = (r_0,\,r_1) = \cdots = (r_{n-1},\,r_n) = (r_n,\,0) = r_n$$

となる。すなわちこのユークリッドの互除法によって、最後の零でない余りが $a$ と $b$ の最大公約数である。

この過程はさらに直接的に有意義な結果をもたらす。互除の最初の等式から $r_0 = a - bq_0$ が得られ、$r_0$ は $a$ と $b$ の整数係数の線形結合

$$r_0 = k_0 a + l_0 b$$

として表せる。ここで $k_0 = 1,\,l_0 = -q_0$ はともに整数である。次の等式に代入すると

$$r_1 = b - r_0 q_1 = b - (k_0 a + l_0 b)q_1 = k_1 a + l_1 b$$

ここで $k_1,\,l_1$ も整数である。この過程を繰り返すと最終的に

$$r_n = (a,\,b) = ka + lb$$

が得られる。ここで $k,\,l$ は整数である。これにより、任意の二つの整数 $a$ と $b$ の最大公約数 $(a,b)$ を求めるだけでなく、方程式 $ka+lb=(a,b)$ の一組の整数解 $k,\,l$ も得られる。次の結論が成り立つ。

定理8（Bezout の定理） 任意の二つの整数 $a$ と $b$ に対して、整数の組 $k,\,l$ が存在して $a$ と $b$ の最大公約数を $a$ と $b$ の整数係数の線形結合として表せる：

$$ka + lb = (a,\,b).$$

この公式を Bezout の公式という。特に $a$ と $b$ が互いに素（$(a,b)=1$）のとき、方程式

$$ka + lb = 1$$

は整数解を持つ。

なお、Bezout の公式はユークリッドの互除法とは独立に証明でき、二つ以上の数の組にも拡張できる。ここでは簡単のため、二つの数の組の Bezout の公式をユークリッドの互除法の帰結とみなす。

Bezout の公式を用いて次の結果が得られる。

系9 $a$ と $b$ を任意の二つの整数とする。

$a$ と $b$ の各公約数はすべてそれらの最大公約数の約数である。
$(ma,\,mb) = m(a,\,b)$。ここで $m$ は任意の正整数である。

証明

$u$ を $a$ と $b$ の公約数とする。すなわち $u\mid a$、$u\mid b$。したがって $u$ は $ka+lb$ をも整除でき、Bezout の公式より $u$ は $(a,b)$ を整除できる。

(2) を証明するために、$d=(a,b)$、$e=(ma,mb)$ とおく。$md\mid ma$、$md\mid mb$ なので (1) より $md\mid(ma,mb)$、すなわち $md\mid e$。

一方 Bezout の公式より整数 $k,\,l$ が存在して $d = ka + lb$ となる。したがって

$$md = mka + mlb = k(ma) + l(mb)$$

より $e\mid md$。合わせると $e = md$。

素数と整数の素因数分解

定義10 $1$ より大きい任意の正整数 $p$ について、$p$ が真の因数を持たない、すなわち $p$ の正の約数が $1$ と $p$ 自身しかないとき、$p$ を素数（または質数）という。そうでない場合を合成数という。

こうして正整数全体は三つの類に分かれる。数 $1$ は単独の類をなし、他に素数の類と合成数の類がある。

素数はたくさん存在する。例えば

$$2,\,3,\,5,\,7,\,11,\,13,\,17,\,19,\,23,\,29,\,31,\,\cdots$$

素数に関する最も古典的な結果は次のものである。

定理11 素数は無数に存在する。

この定理の証明は紀元前 3 世紀にすでに Euclid によって与えられており、証明の方法は今日でも数学的推論の典範であり、今日「背理法」と呼ばれるものである。

証明

定理が成立しないと仮定する。すなわち素数の個数が有限個しかないと仮定し、$p_1,\,p_2,\,\cdots,\,p_n$ がすべての有限個の素数を表すとする。整数

$$N = p_1 p_2 \cdots p_n + 1$$

を考えると、$N > 1$ かつ $N \neq p_j$（$j=1,\cdots,n$）であるから $N$ は合成数であり、素因数 $p$ を持つ。すでに仮定したすべての素数がここにあるから $p$ は必ず $p_1,\,\cdots,\,p_n$ の中の一つに等しく、したがって $p$ は $N - p_1 p_2 \cdots p_n = 1$ を整除できる。つまり $p$ が $1$ を整除することになり、これは明らかに矛盾した結論である。矛盾をもたらした原因は仮定であるから、仮定は誤りであり、その否定が正しい。

素数の重要性は次の事実にある。すなわち$1$ より大きい任意の正整数はすべて素数の積として表せる。$1$ より大きい整数 $p$ について、それが合成数であれば必ず非自明な約数 $p = p_1 p_2$ を持ち、$p_1$ と $p_2$ の少なくとも一方が合成数なら引き続き分解できる。このような分解は有限歩で終わり、これ以上分解できなくなるまで続ける。

一つの整数を素数の積に分解した後、整数の乗法の交換性により、これらの素因数の積の順序は重要でない。では順序を問わないとき、一つの整数の素因数分解は一意的か。答えは肯定的であり、次の算術の基本定理と呼ばれる定理が成立する。

定理12（算術の基本定理） $1$ より大きい各正整数は有限個の素数の積に分解でき、素因数の順序を問わなければ分解は一意的である。

引き続き Euclid の証明方法を採用するため、いくつかの準備をする。

補題13 $p$ を素数、$a$ と $b$ を二つの整数とする。もし $p$ が $ab$ を整除できるならば、$p$ は $a$ と $b$ の少なくとも一方を整除できる。

より一般に、$p$ を素数、$a_1,\,a_2,\,\cdots,\,a_n$ を $n$ 個の整数とする。もし $p$ が $a_1 a_2 \cdots a_n$ を整除できるならば、$p$ は $a_1,\,a_2,\,\cdots,\,a_n$ の少なくとも一つを整除できる。

証明

素数 $p$ の約数は $1$ と $p$ 自身しかない。もし $p$ が $a$ を整除できないとすると、二者は互いに素 $(a,\,p)=1$ である。Bezout の公式より整数 $k,\,l$ が存在して

$$1 = ka + lp.$$

両辺に $b$ を掛けると

$$b = kab + lpb.$$

$p$ が $ab$ を整除するので $ab = pr$ となり、

$$b = kpr + lpb = p(kr + lb)$$

すなわち $p$ が $b$ を整除できる。こうして $p$ が $a$ を整除できないならば必ず $b$ を整除できる。つまり $p$ は $a$ と $b$ の少なくとも一方を整除できる。

第二の命題の証明は帰納法による。$n=2$ のとき、すなわち二つの数の場合は証明済みである。

$p$ が $a_1 \cdots a_{n-1}$ を整除するとき $p$ は $a_1,\,\cdots,\,a_{n-1}$ の少なくとも一つを整除すると仮定しよう。

$p$ が $a_1 \cdots a_{n-1} a_n = (a_1 \cdots a_{n-1})a_n$ を整除するとき、$n=2$ の場合より $p$ は $a_1 \cdots a_{n-1}$ と $a_n$ の少なくとも一方を整除できる。もし $p$ が $a_n$ を整除するならば結論が得られる。もし $p$ が $a_1 \cdots a_{n-1}$ を整除するならば、帰納仮定より $p$ は $a_1,\,\cdots,\,a_{n-1}$ の少なくとも一つを整除できる。どちらの場合も $p$ は必ず $a_1,\,\cdots,\,a_{n-1},\,a_n$ の少なくとも一つを整除できる。

算術の基本定理の証明 上記の補題を踏まえ、正整数 $a$ に二つの素因数分解があると仮定する：

$$a = p_1 \cdots p_r = q_1 \cdots q_s.$$

ここで $p_1,\,\cdots,\,p_r$ と $q_1,\,\cdots,\,q_s$ はすべて素数である。明らかに $p_1$ は左辺を整除でき、当然右辺も整除できる。すなわち $p_1$ は $q_1 \cdots q_s$ を整除できる。補題より $p_1$ は $q_1,\,\cdots,\,q_s$ の少なくとも一つを整除できる。$q_k$ を $p_1$ が整除できるものとすると、$q_k$ は素数なので $q_k = p_1$ となり、両辺からこの共通素因数を消去して残りの部分に同じ過程を続けると、最終的に $p_1,\,\cdots,\,p_r$ は $q_1,\,\cdots,\,q_s$ の一部であるから $r \leqslant s$ となる。

同じ操作を $q_1,\,\cdots,\,q_s$ に対して行うと $s \leqslant r$ かつ $q_1,\,\cdots,\,q_s$ が $p_1,\,\cdots,\,p_r$ の一部であることが分かる。合わせると二者は完全に一致する。$\square$

算術の基本定理は正整数に対するものだが、すべての整数にも容易に拡張でき、等しい素因数をまとめると次の定理が得られる。

定理14（標準分解） 任意の整数 $n$ は一意的に次の形に分解できる：

$$n = \varepsilon\, p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$

ここで $\varepsilon = \pm 1$、$p_1,\,\cdots,\,p_k$ は二つずつ異なる素数、$\alpha_1,\,\cdots,\,\alpha_k$ は正整数である。また $\alpha_j$ を分解における素因数 $p_j$ の重複度と呼ぶ（$j=1,\,\cdots,\,k$）。

以上の議論を通じて、素数は正整数を構成する最も基本的な単位であることが分かる。物質を構成する基本粒子のようなもの、あるいは人類の「遺伝子」のようなものである。人々は自然に次の問いを立てる。多数の正整数の中からどのようにしてすべての素数を篩い出すか。ある表示式によって素数を生成できるか。正整数全体の中で素数の分布の「地図」はあるか。

まず正整数の中から素数を篩い出す方法を見てみよう。古くて単純な方法として、与えられた数 $n$ より小さい数を $1,\,2,\,3,\,\cdots,\,n$ の順に並べ、2 の倍数（2 自身を含まない）をすべて消去し、次に 3 の倍数（3 自身を含まない）を消去し、同様に続けて残ったものが $n$ 以内の素数である。この過程を「Eratosthenes（エラトステネス，紀元前 274--194 年頃）の篩」と呼ぶ。

もう一つの考えは素数を生成する数学的公式を研究することである。Fermat（フェルマー，1601--1665）はかつて次の公式を提唱した：

$$F(n) = 2^{2^n} + 1$$

（この公式が与える数を「Fermat 数」と呼ぶことが多い）。$n=1,\,2,\,3,\,4$ のとき Fermat 数は素数であることが確認できるが、$n=5$ のとき Fermat 数は合成数であり

$$2^{2^5} + 1 = 641 \cdot 6700417.$$

他にも素数を生成できる簡潔な公式がある。例えば

$$f(n) = n^2 - n + 41.$$

$n = 1,\,2,\,\cdots,\,40$ のとき $f(n)$ はすべて素数であるが、$f(41) = 41^2$ はもはや素数ではない。公式

$$f(n) = n^2 - 79n + 1601$$

は $n=1$ から $n=79$ までがすべて素数だが、$n=80$ のとき素数でなくなる。

素数を求める規則的な公式は誰も見つけていないが、$n$ 以内の素数の「密度」（または「平均分布」）には一定の規則性があることが分かっている。

$A_n$ が $n$ 以内の素数の個数を表すとすると、$A_n/n$ は $1/\ln n$ に近似し、しかも $n$ が大きくなるほどこの近似はより精確になる。詳細はここでは論じない。

Euler（オイラー，1707--1783）はもう一つの問題、すなわち任意の正整数 $n$ 以内の $n$ と互いに素な正整数の個数を研究した。このために Euler は次の関数を定義した。

定義15 任意の正整数 $n$ に対して、$n$ 以内（すなわち $1$ から $n$ まで）かつ $n$ と互いに素な正整数の個数を $\varphi(n)$ で表す。これを Euler 関数という。

例えば $\varphi(1) = 1$ であり、$\varphi(12) = 4$ である。なぜなら $12$ を超えない正整数の中で $12$ と互いに素なものは $1,\,5,\,7,\,11$ だけだからである。Euler 関数をさらに研究するために、まず次の補題を示す。

補題16 任意の素数 $p$ と正整数 $\alpha$ に対して

$$\varphi(p) = p - 1, \qquad \varphi(p^\alpha) = p^\alpha - p^{\alpha-1} = p^\alpha\!\left(1 - \frac{1}{p}\right).$$

証明

$\varphi(p) = p-1$ は明らかである。正整数 $\alpha > 1$ として、$1$ から $p^\alpha$ の中で $p$ の倍数は

$$p,\,2p,\,3p,\,\cdots,\,p^{\alpha-1}p,$$

全部で $p^{\alpha-1}$ 個ある。$1$ から $p^\alpha$ の中からこれらの $p$ の倍数を除いた残りはすべて $p^\alpha$ と互いに素であり、互いに素な数の個数は $p^\alpha - p^{\alpha-1}$ 個となる。こうして第二の等式が証明された。

次の定理は一般的な $n$ に対しても Euler 関数の値が厳密に計算できることを示す。

定理17（Euler の定理） 任意の正整数 $n$ に対して、$n$ の素因数分解を

$$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$

とする。ここで $p_1,\,p_2,\,\cdots,\,p_k$ は $n$ の二つずつ異なる素因数、$\alpha_j$（$j=1,\,\cdots,\,k$）は素因数 $p_j$ の重複度である。このとき Euler 関数の $n$ における値は

$$\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right).$$

証明

証明を以下の手順で行う。

(1) $1$ から $n$ の中で $p_1$ の倍数は $p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} = \dfrac{n}{p_1}$ 個あり、それぞれ

$$p_1,\,2p_1,\,3p_1,\,\cdots,\,\frac{n}{p_1}p_1.$$

したがってこれらの $p_1$ の倍数を排除して、$1$ から $n$ の中で $p_1$ と互いに素な整数の個数は

$$n - \frac{n}{p_1} = n\!\left(1 - \frac{1}{p_1}\right).$$

(2) 同様に $1$ から $n$ の中で $p_2$ の倍数は $\dfrac{n}{p_2}$ 個である：

$$p_2,\,2p_2,\,3p_2,\,\cdots,\,\frac{n}{p_2}p_2,$$

しかしその中のいくつかは $p_1$ の倍数でもある。これらの $p_1$ の倍数は

$$1,\,2,\,3,\,\cdots,\,\frac{n}{p_2}$$

の中に現れる（$p_1$ と $p_2$ は互いに素なので）。これらの重複を除くと、残った数は $p_2$ の倍数だが $p_1$ と互いに素な数、つまり $1,\,2,\,3,\,\cdots,\,\dfrac{n}{p_2}$ の中で $p_1$ と互いに素な数であり、(1) によればその個数は $\dfrac{n}{p_2}\!\left(1 - \dfrac{1}{p_1}\right)$ 個である。

$1$ から $n$ の中で $p_1$ と互いに素な数から、さらに $p_2$ の倍数だが $p_1$ と互いに素な数を排除すると、$p_1$ と $p_2$ の両方と互いに素な数の個数は

$$n\!\left(1 - \frac{1}{p_1}\right) - \frac{n}{p_2}\!\left(1 - \frac{1}{p_1}\right) = n\!\left(1 - \frac{1}{p_1}\right)\!\left(1 - \frac{1}{p_2}\right).$$

(3) $1$ から $n$ の中で $p_3$ の倍数は $\dfrac{n}{p_3}$ 個である：

$$p_3,\,2p_3,\,3p_3,\,\cdots,\,\frac{n}{p_3}p_3,$$

その中のいくつかは $p_1$ または $p_2$ の倍数であり、(1) と (2) の中でそれらはすでに排除されている。同様に $p_1,\,p_2,\,p_3$ が互いに素なので、これらの数は

$$1,\,2,\,3,\,\cdots,\,\frac{n}{p_3}$$

の中に現れる。したがってそれらを除去すると、$1$ から $n$ の中で $p_1,\,p_2,\,p_3$ すべてと互いに素な数の個数は

$$n\!\left(1 - \frac{1}{p_1}\right)\!\left(1 - \frac{1}{p_2}\right) - \frac{n}{p_3}\!\left(1 - \frac{1}{p_1}\right)\!\left(1 - \frac{1}{p_2}\right) = n\!\left(1 - \frac{1}{p_1}\right)\!\left(1 - \frac{1}{p_2}\right)\!\left(1 - \frac{1}{p_3}\right).$$

同じ手順で逐次進めると、定理の結果が得られる。

Euler の定理からさらに Euler 関数が満たす一つの性質が得られる。この性質は Euler 関数の積性とも呼ばれる。

系18 任意の二つの正整数 $m,\,n$ について、$(m,\,n) = 1$ ならば

$$\varphi(mn) = \varphi(m)\varphi(n).$$

証明

$m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$、$n = q_1^{\beta_1} q_2^{\beta_2} \cdots q_l^{\beta_l}$ とする。$(m,\,n) = 1$ なので二つの正整数の素因数は重複しない。Euler の定理を用いると $\varphi(mn) = \varphi(m)\varphi(n)$ が直ちに得られる。

合同と合同類

固定した正整数 $m$ に対して、整数の除法より任意の整数を $m$ で割った余りは $0,\,1,\,\cdots,\,m-1$ の中の一つしかあり得ない。したがってすべての整数をそれらが $m$ で割られた後の余りによって分類することができる。これが以下の合同類の定義である。

定義19 二つの整数 $a$ と $b$ を $m$ で割った余りが等しいとき、すなわち $a-b$ が $m$ で整除される（$m\mid(a-b)$）とき、それらは $m$ を法として「合同」であるという。標準的な言い方は $a$ と $b$ は法 $m$ について合同あるいは $a$ は法 $m$ において $b$ と合同といい、$m$ を法という。

$$a \equiv b \pmod{m}$$

と記し、（法 $m$ の）合同式という。$m\nmid(a-b)$ ならば $a$ と $b$ は法 $m$ で合同でないという。二つの数 $a$ と $b$ が合同となるのは次と同値である：

$$m\mid(a-b), \quad\text{または}\quad a = b + rm.$$

二つの数の間の合同関係は通常の二つの数が等しいこととよく似た性質を持つ。以下にそれらをまとめる。

性質20

（反射性） $a \equiv a \pmod{m}$。
（対称性） $a \equiv b \pmod{m}$ ならば $b \equiv a \pmod{m}$。
（推移性） $a \equiv b \pmod{m}$、$b \equiv c \pmod{m}$ ならば $a \equiv c \pmod{m}$。

$a \equiv a' \pmod{m}$、$b \equiv b' \pmod{m}$ とすると

$a \pm b \equiv a' \pm b' \pmod{m}$。
$ab \equiv a'b' \pmod{m}$。
$m$ が素数のとき、$a \equiv 0 \pmod{m}$ または $b \equiv 0 \pmod{m}$ となるのは $ab \equiv 0 \pmod{m}$ のときに限る。

証明

(1)、(2)、(3) は定義から直接証明できる。

(4) と (5) については、合同の同値条件より $a = a' + rm$、$b = b' + sm$ となるから

$$a \pm b = a' \pm b' + (r \pm s)m, \qquad ab = a'b' + (srm \pm a's \pm b'r)m$$

が成立し証明が完成する。

(6) について：$m\mid a$ または $m\mid b$ ならば $m\mid ab$ は明らかである。逆に $m\mid ab$ ならば、$m$ は $a,\,b$ の少なくとも一方を整除できる（補題13 による）。

以下は法に関するいくつかの簡単で実用的な定理である。

定理21

$ac \equiv bc \pmod{m}$ ならば
$$a \equiv b \left(\bmod\ \frac{m}{(c,m)}\right).$$
特に $(c,\,m)=1$ のとき $a \equiv b \pmod{m}$。
$a \equiv b \pmod{m}$、$d\mid m$ ならば $a \equiv b \pmod{d}$。

証明

$m_1 = (c,m)$、$m_2 = \dfrac{m}{(c,m)}$ とおくと $m = m_1 m_2$、$c = km_1$ となる。既知の条件より

$$m\mid(a-b)c, \quad\text{すなわち}\quad m_1 m_2 \mid (a-b)km_1,$$

両辺を $m_1$ で割って $m_2\mid(a-b)k$ を得る。$c = km_1$ で $m_1 = (c,m)$ だから $(k,\,m_2) = 1$ であり、したがって $m_2\mid(a-b)$ となる。

特に $m_1 = (c,m) = 1$ のとき $m = m_2$ で $c$ を整除できないため、$m_2\mid(a-b)$ となる。

$d\mid m$ のとき $m = dm_1$ とおく。$m\mid(a-b)$ ならば整数 $k$ が存在して $a-b = mk = dm_1 k$ となり $d\mid(a-b)$ が導かれる。

定義22 集合 $E$ の元の間にある関係 $a \sim b$（$a,\,b\in E$）が存在するとき、この関係が次を満たすならば

反射性：$a \sim a$、$a \in E$；
対称性：$a \sim b$ ならば $b \sim a$；
推移性：$a \sim b$、$b \sim c$ ならば $a \sim c$；

この関係を同値関係という。二つの元が同値関係 $a \sim b$ にあることを $a$ と $b$ が互いに同値であるともいう。

したがって性質20 の (1)(2)(3) は整数間の法 $m$ の合同関係が一種の同値関係であることを示している。平面上の三角形の間の相似関係は同値関係であり、二つの数が等しいという関係も当然同値関係である。性質20 の (4) と (5) はさらに、同じ法 $m$ に対して合同関係は等号関係と同じように加法・減法・乗法を保つことを示している。等号関係については

$$ab = 0 \iff a = 0 \text{ または } b = 0.$$

という結果があるが、合同関係については法 $m$ に制限を加える必要があり、性質20 の (6) によれば法が素数でなければ上記の結論は成立しない。例えば

$$8 \equiv 2 \pmod{6},\quad 9 \equiv 3 \pmod{6},\quad\text{しかし}\quad 72 \equiv 0 \pmod{6}.$$

一般に、同値関係 $\sim$ は集合 $E$ の元を互いに同値なものを一つの類にまとめて分類し、関係 $\sim$ の同値類と呼ぶ。

同様に、合同関係も整数を法 $m$ での余りに応じていくつかの互いに交わらない類（「族」）に分類できる。同一の類の任意の二つの整数（類の元）は法 $m$ で合同であり、異なる類の二つの整数（元）は法 $m$ で合同でない。このような各類を法 $m$ の合同類という。具体的に一つの整数 $a$ について、$a$ が属する合同類を $[a](\bmod\ m)$ または単に $[a]$ と記し、この類は法 $m$ で $a$ と合同なすべての整数を含む：

$$[a] = \{x \mid x \in \mathbb{Z},\; x \equiv a \pmod{m}\}.$$

$a$ をこの類の代表元という。

$a \equiv b \pmod{m}$ ならば $a$ と $b$ は同一の類に属するから $[a] = [b]$。逆に $[a]$ と $[b]$ が $a$ と $b$ を代表元とする二つの交わらない類であれば、$a$ と $b$ は法 $m$ で合同でない。

整数の除法によれば、任意の整数は $\{0,\,1,\,2,\,\cdots,\,m-1\}$ の中の何れかの数と法 $m$ で合同であり、$\{0,\,1,\,2,\,\cdots,\,m-1\}$ の内の任意の二つの数は法 $m$ で合同でない。したがって法 $m$ はちょうど $m$ 個の合同類を持ち、それぞれ余り $0,\,1,\,2,\,\cdots,\,m-1$ を代表元とする。これらの合同類からなる集合を

$$\mathbb{Z}_m = \{[0],\,[1],\,[2],\,\cdots,\,[m-1]\}$$

と記す。

これは「類」を元とする集合であり、元の個数は $m$ 個である。例えば $m=2$ のとき、法 2 の合同類はただ二つあり、一つは法 2 で 0 と合同なすべての整数の集合 $[0]$（すなわちすべての偶数の類）であり、もう一つは法 2 で 1 と合同なすべての整数の集合 $[1]$（すなわちすべての奇数の類）である。集合

$$\mathbb{Z}_2 = \{[0],\,[1]\}$$

は二つの元を持ち、一つは偶数の類、もう一つは奇数の類である。

興味深いことに、合同の性質20 によって集合 $\mathbb{Z}_m$ の元の加法・減法・乗法を定義できる。

合同類の加減法 $[a],\,[b] \in \mathbb{Z}_m$ とする。法 $m$ の合同類 $[a \pm b]$ を $[a]$ と $[b]$ の和（差）として定義する：

$$[a] \pm [b] = [a \pm b].$$

まずこの定義の妥当性を確かめる必要がある。すなわちどのような代表元を選んでも二つの類の加減が一意的に確定することを確かめる。例えば $[a]$ と $[b]$ の中からそれぞれ別の代表元 $a' \in [a]$、$b' \in [b]$ を選ぶと、$a \equiv a' \pmod{m}$、$b \equiv b' \pmod{m}$ となり、性質20 の (4) より

$$a \pm b \equiv a' \pm b' \pmod{m}$$

すなわち $a' \pm b'$ と $a \pm b$ は同一の類に属し、$[a' \pm b'] = [a \pm b]$ となる。

合同類の乗法 同様に $[a]$ と $[b]$ の積を次のように定義できる：

$$[a][b] = [ab],$$

性質20 の (5) によりこのように定義された類の間の積は代表元の選び方によらない。

合同類における零元と単位元 合同類 $[0]$ と $[1]$ をそれぞれ $\mathbb{Z}_m$ の零元と単位元と呼び、それぞれ次を満たす：

$$[a] + [0] = [0] + [a] = [a], \qquad [1][a] = [a][1] = [a].$$

上記のように定義した合同類の間の加法と乗法が交換律・結合律・乗法の加法に対する分配律を満たすことは容易に検証できる。

したがって $\mathbb{Z}_m$ は有限個の元しか持たないが、$\mathbb{Z}_m$ は整数集合 $\mathbb{Z}$ と同様の演算規則を持つので、加法群かつ交換環であり、法 $m$ の合同類環と呼ばれる。

$\mathbb{Z}_5 = \{[0],\,[1],\,[2],\,[3],\,[4]\}$ を例として、元の間の加法と乗法の表を以下に示す。

加法	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
$[0]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
$[1]$	$[1]$	$[2]$	$[3]$	$[4]$	$[0]$
$[2]$	$[2]$	$[3]$	$[4]$	$[0]$	$[1]$
$[3]$	$[3]$	$[4]$	$[0]$	$[1]$	$[2]$
$[4]$	$[4]$	$[0]$	$[1]$	$[2]$	$[3]$

乗法	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
$[2]$	$[0]$	$[2]$	$[4]$	$[1]$	$[3]$
$[3]$	$[0]$	$[3]$	$[1]$	$[4]$	$[2]$
$[4]$	$[0]$	$[4]$	$[3]$	$[2]$	$[1]$

幾何的に見ると、整数 $\mathbb{Z}$ は実数直線上のすべての整数点に対応する。すなわち長さ 1 の等間隔の点である（図 1）。

図 1

一方 $\mathbb{Z}_m$ に対応するのは円上の $m$ 個の等分点であり、例えば時計の 12 個の目盛りはまさに $\mathbb{Z}_{12}$ の元に対応する点である。12 時間ごとに針は同じ位置を指す。例えば 3 時・15 時・27 時などはすべて $[3]$ の位置を指すが、これは $3,\,15,\,27,\,\cdots$ が法 12 で合同であり、法 12 の合同類 $[3]$ に属するからである（図 2）。

図 2

$\mathbb{Z}_m$ の元が乗法のもとで可逆かどうかについては、さらに詳しく議論する必要がある。

まず有理数 $\mathbb{Q}$ において、零でない有理数 $\alpha$ の逆元とは方程式 $\alpha x = 1$ が $\mathbb{Q}$ において唯一の解を持つことを指す。この解 $x$ を有理数 $\alpha$ の逆元と呼び、$x = \alpha^{-1} \in \mathbb{Q}$ と記す。

しかし $\mathbb{Z}_m$ において、すべての零でない元 $[a]$ に対して方程式 $[a][x]=[ax]=[1]$ が $\mathbb{Z}_m$ 中に必ずしも解を持つわけではない。つまり $[a]$ は $\mathbb{Z}_m$ において必ずしも逆元を持つとは限らない。例えば $\mathbb{Z}_6$ の $[2]$ については $[x]$ が存在して $[2][x]=[2x]=[1]$ となることはない。なぜなら $2x \equiv 1 \pmod{6}$ となる整数 $x$ が存在しないからである。

また $\mathbb{Z}_6$ の二つの零でない元 $[2]$ と $[3]$ について $[2][3]=[0]$ となり、$\mathbb{Z}_6$ の $[2]$ と $[3]$ はいずれも逆元を持てない。

しかし $\mathbb{Z}_m$ の部分集合

$$\mathbb{Z}_m^* = \{[a] \mid [a] \in \mathbb{Z}_m,\; (a,m)=1\}$$

を考えると、$\mathbb{Z}_m^*$ の元はすべて逆元を持つ。すなわち $(a,m)=1$ のときに限り $[a]$ は可逆で $[a]^{-1} \in \mathbb{Z}_m^*$ となる。

定理23 集合 $\mathbb{Z}_m^*$ の元は次を満たす。

$[1] \in \mathbb{Z}_m^*$。
$[a],[b] \in \mathbb{Z}_m^*$ ならば $[a][b] \in \mathbb{Z}_m^*$。
$[a] \in \mathbb{Z}_m^*$ ならば方程式 $[a][x]=[1]$ は $\mathbb{Z}_m^*$ 中に唯一の解を持ち、$[x]=[a]^{-1}$ と記す。

上述の三条件を満たす集合を乗法群という。したがって $\mathbb{Z}_m^*$ は（可換な）乗法群であり、その元の個数は $1,2,\cdots,m$ の中で $m$ と互いに素な整数の個数、すなわち $\varphi(m)$（定義15 の Euler 関数）である。

証明

(1) は明らかである。$(1,m)=1$ だからである。

(2) については、$(a,m)=1$、$(b,m)=1$ ならば $(ab,m)=1$ という単純な事実を使うだけでよい。

(3) の証明は次のとおりである。任意の $[a] \in \mathbb{Z}_m^*$ に対して $(a,m)=1$ であるから

$$0 \cdot a,\; 1 \cdot a,\; 2 \cdot a,\; \cdots,\; (m-1)a$$

この $m$ 個の数は法 $m$ で互いに合同でない。なぜなら任意の $r,\, s$（$0 \leqslant r < s \leqslant m-1$）について $sa - ra = (s-r)a$ は、$s-r$ も $a$ も $m$ で整除できないからである。また任意の $ra$ も法 $m$ で 0 と合同にならない（$r \neq 0$ のとき）。

したがってこの $m$ 個の数が属する合同類は合わせて $m$ 個あり、$\mathbb{Z}_m$ と一致する：

$$\{[0],\,[a],\,[2a],\,\cdots,\,[(m-1)a]\} = \mathbb{Z}_m.$$

これはすなわち、$[ka]=[1]$ となる唯一の $k \in \{0,1,\cdots,m-1\}$ が存在すること、すなわち $ka \equiv 1\pmod{m}$ となる唯一の $k$ が存在することを意味し、したがって $[x]=[k]$ が方程式 $[a][x]=[1]$ の唯一の解である。

$m \mid ka-1$、$(a,m)=1$ であるから $(k,m)=1$、すなわち解 $[x]=[k] \in \mathbb{Z}_m^*$ である。

例5.1 $m=5$ のとき

$$\mathbb{Z}_5^* = \{[1],[2],[3],[4]\}$$

であり、各元の逆元はそれぞれ $[1]^{-1}=[1]$、$[2]^{-1}=[3]$、$[3]^{-1}=[2]$、$[4]^{-1}=[4]$ である。

$m=12$ のとき

$$\mathbb{Z}_{12}^* = \{[1],[5],[7],[11]\}$$

であり、各元の逆元はそれぞれ $[1]^{-1}=[1]$、$[5]^{-1}=[5]$、$[7]^{-1}=[7]$、$[11]^{-1}=[11]$ である。

$m=14$ のとき

$$\mathbb{Z}_{14}^* = \{[1],[3],[5],[9],[11],[13]\}$$

であり、各元の逆元はそれぞれ $[1]^{-1}=[1]$、$[3]^{-1}=[5]$、$[5]^{-1}=[3]$、$[9]^{-1}=[11]$、$[11]^{-1}=[9]$、$[13]^{-1}=[13]$ である。

したがって $\mathbb{Z}_m$ の $[0]$ 以外のすべての元が可逆となるのは $m=p$ が素数のときに限る。なぜならこのとき $0$ 以外の $1,2,\cdots,p-1$ はすべて $p$ と互いに素であり、$\mathbb{Z}_p = \{[0]\} \cup \mathbb{Z}_p^*$ となるからである。

定理24 $p$ を任意の素数とする。$\mathbb{Z}_p$ の元は次を満たす。

任意の $[a],[b] \in \mathbb{Z}_p$ に対して $[a]\pm[b]=[a\pm b]\in\mathbb{Z}_p$、$[a][b]\in\mathbb{Z}_p$。
$\mathbb{Z}_p$ は零元 $[0]$ と単位元 $[1]$ を持つ。すなわち任意の $[a]\in\mathbb{Z}_p$ に対して $[a]+[0]=[a]$、$[a][1]=[a]$。
$\mathbb{Z}_p$ の任意の零でない $[a]$ に対して逆元 $[x]=[a]^{-1}\in\mathbb{Z}_p$ が存在し
$$[a][a]^{-1} = [a]^{-1}[a] = [1].$$

上述の三条件を満たす集合を体（field）という。したがって素数 $p$ に対して $\mathbb{Z}_p$ は体である。$\mathbb{Z}_p$ は $p$ 個の合同類から構成されるので有限体という。

まとめると、合同類の議論を通じて次のいくつかの数学概念に触れた。

加法・乗法、および交換律・結合律・分配律を満たし零元と単位元を持つ集合を（交換）環という。

乗法と除法（乗法の逆演算）、および交換律・結合律を満たし単位元を持つ集合を（可換）乗法群という。

交換環でかつ乗法群（零元の除法を除く）である集合を体という。

私たちになじみのある集合（数集合）について言えば、整数集合 $\mathbb{Z}$ は環だが体ではなく、有理数集合 $\mathbb{Q}$ と実数集合 $\mathbb{R}$ は体である。

$\mathbb{Z}$ であれ $\mathbb{Q}$ であれ $\mathbb{R}$ であれ、その元の個数はすべて無限個である。ここでは整数の合同類を通じて、元の個数がただ有限個（$p$ は素数）の有限体の古典的な例を与えた。

最後に一つの重要な定理とその証明を述べる。

定理25（Fermat の小定理） $a$ を整数とする。$p$ が $a$ を整除できない任意の素数（$p\nmid a$）ならば

$$a^{p-1} \equiv 1 \pmod{p} \quad\text{または}\quad a^p \equiv a \pmod{p}.$$

証明

$a$ の倍数を考える：

$$m_1 = a,\; m_2 = 2a,\; \cdots,\; m_{p-1} = (p-1)a.$$

これらの数はいかなる二つも法 $p$ で合同にならない。なぜなら任意の $m_r,\,m_s$（$1\leqslant r<s\leqslant p-1$）について $m_s - m_r = (s-r)a$ は、$s-r$ も $a$ も $p$ で整除できないからである。また任意の $m_r = ra$ も法 $p$ で 0 と合同にならない。

以上の分析より $m_1,m_2,\cdots,m_{p-1}$ の $p-1$ 個の数を $p$ で割った余りは二つずつ異なりかつ 0 でないから、余りはただ $1,2,\cdots,p-1$ のみでありうる。順序通りに対応するとは限らないが、合同の性質20 の (5) より

$$m_1 m_2 \cdots m_{p-1} \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.$$

ここで $m_1 m_2 \cdots m_{p-1} = 1 \cdot 2 \cdots (p-1) \cdot a^{p-1} = (p-1)!\, a^{p-1}$ であることに注意すると、上の二式から

$$(p-1)!\,(a^{p-1}-1) \equiv 0 \pmod{p}.$$

しかし $p$ は $(p-1)!$ を整除できないため、性質20 の (6) より $p$ は $a^{p-1}-1$ のみを整除できる。すなわち $a^{p-1} - 1 \equiv 0 \pmod{p}$。

合同方程式（組）

与えられた正整数 $m$ と $n$ 次整数係数多項式

$$f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$$

に対して、次の方程式

$$f(x) \equiv 0 \pmod{m}$$

を法 $m$ の $n$ 次合同方程式という。明らかに $x=c$ が方程式の一つの解ならば、合同類 $[c]$ の中の任意の数（$c+km$ の形の数、$k$ は任意の整数）はすべて方程式の解である。同一の合同類に属する解を同一の解とみなし、法 $m$ で合同でない解のみを異なる解とみなす。合同方程式組とは、与えられた $r$ 個の正整数 $m_1,\cdots,m_r$ および $r$ 個の整数係数多項式 $f_1(x),\cdots,f_r(x)$ に対して、法 $m_i$ の合同方程式の連立方程式組

$$f_i(x) \equiv 0 \pmod{m_i},\quad i=1,2,\cdots,r$$

をいう。以下では一次合同方程式（組）の解法を主に論じる。

定理26 $m$ と $a$、$b$ を与える。一次合同方程式

$$ax \equiv b \pmod{m}$$

を考える。

$(a,m)=1$ ならば方程式には唯一の解が存在する。
$(a,m)=d$ ならば、方程式の解が存在するための必要十分条件は $d\mid b$ である。この条件が成立するとき、ちょうど $d$ 個の解がある。

証明

(1) Bezout の定理8 より整数 $k,l$ が存在して

$$ka + lm = 1.$$

両辺に $b$ を掛けると $kba + lbm = b$ が得られ、$m\mid(kba-b)$ であるから $x=kb$ が方程式の解である。

方程式にもう一つの解 $x'$ があれば $m\mid a(x-x')$、$(a,m)=1$ より $m\mid(x-x')$、すなわち $x\equiv x'\pmod{m}$ となり、解は唯一である。

(2) 方程式に解 $x$ があれば $m\mid(ax-b)$、したがって $d\mid(ax-b)$。$d\mid a$ であるから $d\mid b$。逆に $d\mid b$ のとき、(1) と同様に Bezout の定理8 より整数 $k,l$ が存在して

$$ka + lm = (a,m) = d,$$

これより $k\dfrac{b}{d}a + l\dfrac{b}{d}m = b$ が得られ、$k\dfrac{b}{d}a \equiv b\pmod{m}$、すなわち $x=k\dfrac{b}{d}$ が解である。

$x_0$ を方程式の一つの解とする。すなわち $m\mid(ax_0-b)$ とすると

$$x_k = x_0 + k\frac{m}{d},\quad k=0,1,\cdots,d-1$$

もすべて方程式の解である。なぜなら $ax_k = ax_0 + k\dfrac{am}{d}$、$\dfrac{a}{d}$ は整数であり

$$ax_k - b = ax_0 - b + k\frac{am}{d}$$

において $m\mid(ax_k-b)$ が成立するからである。また

$$x_k - x_{k'} = (k-k')\frac{m}{d}$$

において $m\nmid(x_k-x_{k'})$（$k\neq k'$）であるから $d$ 個の解は法 $m$ で互いに異なる。したがって方程式には $d$ 個の解がある。

中国には 3〜5 世紀頃の数学書『孫子算経』があり、次のような問題が載っている。

問題（孫子算経） 今、物があって数が分からない。3 つずつ数えると余り 2、5 つずつ数えると余り 3、7 つずつ数えると余り 2。この物はいくつか。

この問題は実際には三つの一次合同方程式の連立方程式組を解く問題である。この物の個数を $N$ とすると、$N$ は次を満たす：

$$N \equiv 2\pmod{3},\quad N \equiv 3\pmod{5},\quad N \equiv 2\pmod{7}.$$

この具体的な問題を少し一般化すると、有名な中国剰余定理となる。

定理28（中国剰余定理） $m_1,m_2,m_3$ を二つずつ互いに素な正整数とする。任意の整数 $b_1,b_2,b_3$ に対して、以下の $x$ についての合同方程式組は必ず解を持つ：

$$x \equiv b_1\pmod{m_1},\quad x \equiv b_2\pmod{m_2},\quad x \equiv b_3\pmod{m_3}. \tag{1}$$

方程式 (1) に解 $x$ があれば、任意の $x + nm_1 m_2 m_3$ も解であるから、一旦解が存在すれば解は一意的でない。

証明

合同方程式組 (1) を三組の合同方程式組に分解する：

$$\begin{aligned}x_1 &\equiv 1\pmod{m_1},\quad x_1 \equiv 0\pmod{m_2},\quad x_1 \equiv 0\pmod{m_3}; \quad (2)\\ x_2 &\equiv 0\pmod{m_1},\quad x_2 \equiv 1\pmod{m_2},\quad x_2 \equiv 0\pmod{m_3}; \quad (3)\\ x_3 &\equiv 0\pmod{m_1},\quad x_3 \equiv 0\pmod{m_2},\quad x_3 \equiv 1\pmod{m_3}. \quad (4)\end{aligned}$$

この三組の合同方程式組 (2)、(3)、(4) がそれぞれ解 $x_1,x_2,x_3$ を持てば、(1) の解は

$$x = b_1 x_1 + b_2 x_2 + b_3 x_3$$

となる。

方程式組 (2) について、条件より $(m_2 m_3,\,m_1)=1$ であり、Bezout の公式より整数 $k_1,l_1$ が存在して

$$k_1(m_2 m_3) + l_1 m_1 = 1$$

を満たす。すなわち $k_1(m_2 m_3) \equiv 1\pmod{m_1}$ となり、$x_1 = k_1 m_2 m_3$ ととると (2) の第一式を満たし、(2) の第二式・第三式は自然に満たされる。したがって $x_1 = k_1 m_2 m_3$ は (2) の一つの解である。

同様にして (3) と (4) の解もそれぞれ得られる：

$$x_2 = k_2(m_1 m_3),\quad x_3 = k_3(m_1 m_2),$$

ここで $k_1$ と同様に $k_2$ と $k_3$ は Bezout の公式を満たす整数係数である：

$$k_2(m_1 m_3) + l_2 m_2 = 1,\quad k_3(m_1 m_2) + l_3 m_3 = 1.$$

上記の証明から分かるように、合同方程式組 (1) を解くことは、最終的にユークリッドの互除法を用いた Bezout の公式（定理8 参照）を求めること、すなわち $k_1,k_2,k_3$ を求めることに帰着される。

孫子の定理の具体的な計算を見てみよう：

$$m_1 = 3,\; m_2 = 5,\; m_3 = 7,\quad b_1 = 2,\; b_2 = 3,\; b_3 = 2.$$

$x_1$ を求めるためには、整数 $k_1,l_1$ で $35k_1 + 3l_1 = 1$ を満たすものを求める。互除法で $35 = 11 \cdot 3 + 2$、$3 = 1 \cdot 2 + 1$ だから $1 = 3 - 2 = 3 - (35 - 11\cdot 3) = 12\cdot 3 - 35$ となり、$k_1 = -1$、$l_1 = 12$。したがって $x_1 = -35 \equiv 70 \pmod{105}$ ととれる。同様に $21k_2 + 5l_2 = 1$ の解は $k_2=1,\,l_2=-4$ より $x_2=21$ となる。$15k_3 + 7l_3 = 1$ の解は $k_3=1,\,l_3=-2$ より $x_3=15$ となる。

したがって孫子の定理の解は

$$x = 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233.$$

明らかにこの問題の解は唯一でなく、$3\cdot5\cdot7=105$ の倍数を引いても解である。こうして最小の正整数解は $x=23$ となる。

興味深いことに 1593 年頃、中国の古代数学者の程大位（1533--1606）がすでに非常に精確な答えを示している。彼は『算法統宗』において、この問題の解法を次の歌訣にまとめた。

三人同行七十稀、五樹梅花廿一枝、七子団円正半月、除百零五便得知。

歌訣の中の「三人」・「五樹」・「七子」はそれぞれ三つの法 3、5、7 を指す。「七十稀（70）」・「廿一枝（21）」・「半個月（15）」は求めた三つの解 $x_1=70$、$x_2=21$、$x_3=15$ を指す。最後の一句の「百零五（105）」は三つの法の積 $3\cdot5\cdot7=105$ を指し、最小正整数解の求め方を示している。中国の古代科学者がすでにユークリッドの互除法に非常に精通していたことが見て取れる。

注記：

一、孫子の定理に類する問題は中国古代にほかにも少なくなく、比較的有名なものに「韓信点兵」や「百鶏問題」などがある。いずれも合同方程式組を解く問題に帰着される。

二、中国剰余定理は $n$ 個の合同方程式を含む方程式組にも拡張できる。$m_1,m_2,\cdots,m_r$ を二つずつ互いに素な正整数とすれば、任意の整数 $b_1,b_2,\cdots,b_r$ に対して次の合同方程式組

$$x \equiv b_1\pmod{m_1},\quad x \equiv b_2\pmod{m_2},\quad\cdots,\quad x \equiv b_r\pmod{m_r}$$

は必ず解を持つ。

多項式

この講の最後に、多項式に関する基本内容を簡単に紹介する。なぜなら多項式は整数と多くの共通点を持ち、また後続の各講においても多項式のこれらの基本内容が繰り返し使われるからである。

多項式とは

$$f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0 \quad (a_n \neq 0)$$

のことをいう。ここで $n$ は正整数であり、多項式の次数と呼び $\deg f = n$ と記す。次数が 0 の多項式を定数多項式、次数が 0 より大きい多項式を非定数多項式という。最高次の項の係数が 1 の多項式をモニック多項式という。

多項式の係数 $a_n,a_{n-1},\cdots,a_0$ は整数でもよく、有理数体 $\mathbb{Q}$、実数体 $\mathbb{R}$、複素数体 $\mathbb{C}$ あるいはその他の体に属してもよい。

なお、多項式の係数が有理数の場合、通分によって整数係数の多項式と同等にすることができる。例えば

$$\frac{1}{3}x^2 + \frac{2}{5}x + 1 = 0$$

は通分後に $5x^2 + 6x + 15 = 0$ となる。したがって多くの場合、有理数係数の多項式ではなく整数係数の多項式を議論する。

整数 $\mathbb{Z}$、あるいはある体 $\mathbb{F}$ の係数からなる多項式を「$\mathbb{Z}$ 上の多項式」あるいは「体 $\mathbb{F}$ 上の多項式」と呼び、整数 $\mathbb{Z}$、あるいは体 $\mathbb{F}$ 上の多項式の全体を $\mathbb{Z}[x]$、あるいは $\mathbb{F}[x]$ と記す。

多項式を次数の低い順から高い順に並べることもある：

$$f(x) = a_0 + a_1 x + \cdots + a_n x^n.$$

これは次数の高い順から低い順に並べるのと本質的な違いはない。

1° 多項式の加法と乗法

同一の体上の二つの多項式

$$\begin{aligned}f(x) &= a_n x^n + a_{n-1}x^{n-1} + \cdots + a_0 \quad (a_n \neq 0),\\ g(x) &= b_m x^m + b_{m-1}x^{m-1} + \cdots + b_0 \quad (b_m \neq 0)\end{aligned}$$

の間には加法と乗法の演算が行え、その結果もまたこの体上の多項式であり、

$$\deg(f+g) \leqslant \deg f + \deg g, \qquad \deg(fg) = \deg f + \deg g.$$

加法と乗法について、多項式の係数が整数集合 $\mathbb{Z}$ に属する場合でも、加法と乗法後の多項式の係数は依然として $\mathbb{Z}$ に属する。

2° 多項式の整除と除法

$\mathbb{F}$ を与えられた体とし、$f(x),g(x)\in\mathbb{F}[x]$、$g(x)\neq 0$ とする。$h(x)\in\mathbb{F}[x]$ が存在して

$$f(x) = g(x)h(x)$$

となるとき、$g(x)$ は $\mathbb{F}[x]$ において $f(x)$ を整除するといい、$g(x)\mid f(x)$ と記す。$g(x)$ は $f(x)$ の因式であり、$f(x)$ は $g(x)$ の倍式という。二つの多項式 $f(x)$、$g(x)$ について $h(x)\mid f(x)$、$h(x)\mid g(x)$ ならば $h(x)$ は $f(x)$、$g(x)$ の公因式という。

整除できない場合のために、次の多項式の除法がある。

定理29 $\mathbb{F}$ を与えられた体とし、$f(x),g(x)\in\mathbb{F}[x]$、$g(x)\neq 0$ とする。$\mathbb{F}[x]$ 上に唯一の多項式の組 $q(x),r(x)$ が存在して

$$f(x) = q(x)g(x) + r(x)$$

を満たし、$r(x)$ は 0 であるか、または $\deg r < \deg g$ を満たす。

証明

$\deg f < \deg g$ のとき $q(x)=0$、$r(x)=f(x)$ ととる。$g(x)=c\neq 0$（定数）のとき $q(x)=\dfrac{1}{c}f(x)$、$r(x)=0$ ととる。したがって

$$n = \deg f \geqslant m = \deg g$$

と仮定し、$f(x)$ と $g(x)$ の先頭係数をそれぞれ $a_n$、$b_m$ と記す。$q_1(x)=\dfrac{a_n}{b_m}x^{n-m}$ ととると

$$f_1(x) = f(x) - q_1(x)g(x)$$

の次数は $\deg f_1 < \deg f$ を満たす。もし $\deg f_1 \geqslant \deg g$ ならば $f_1(x)$ に対して上の操作を繰り返す。こうして多項式の列

$$f_0(x)=f(x),\; f_1(x),\; f_2(x),\;\cdots \quad\text{と}\quad q_1(x),\; q_2(x),\;\cdots$$

が得られ、

$$f_{i+1}(x) = f_i(x) - q_{i+1}(x)g(x),\quad i=0,1,2,\cdots$$

かつ

$$\deg f > \deg f_1 > \deg f_2 > \cdots \geqslant \deg g$$

を満たす。この過程は有限歩で必ず停止し、$\deg f_l < \deg g$ となる $l$ が存在する。$q(x)=q_1(x)+\cdots+q_l(x)$ と $r(x)=f_l(x)$ が定理の表示を与える。

もう一組の表示 $f(x) = q_1(x)g(x)+r_1(x)$、$f(x)=q_2(x)g(x)+r_2(x)$ があれば $(q_1(x)-q_2(x))g(x)=r_1(x)-r_2(x)$ が導かれ、両辺の次数を比較すると $q_1(x)=q_2(x)$、$r_1(x)=r_2(x)$ となり一意性が証明される。

整数は除法が自由にできないから、上述の定理は係数が整数（整数係数）の多項式 $f(x),g(x)\in\mathbb{Z}[x]$、$g(x)\neq 0$ には適用できない。しかし $g(x)$ の最高次係数を 1 に限定すれば、上述の証明過程と結論は整数係数多項式にも適用できる。

この除法を通じて次の定理が証明できる。

定理30 $J$ を $\mathbb{F}[x]$ の一つの空でない部分集合とする。$J$ が次の条件を満たすならば、

任意の $f(x),g(x)\in J$ に対して $f(x)-g(x)\in J$；
任意の $f(x)\in J$ と任意の $h(x)\in\mathbb{F}[x]$ に対して $f(x)h(x)\in J$；

すなわち $J=\{0\}$ であるか、または $\mathbb{F}[x]$ の中に最高次係数が 1 の多項式 $d(x)$ が唯一存在して $J=\langle d(x)\rangle$ となる。ここで

$$\langle d(x)\rangle = \{h(x)d(x) \mid h(x)\in\mathbb{F}[x]\}.$$

このような $d(x)$ は $J$ に属する。すなわち、上述の二条件を満たす集合 $J$ の多項式は 0 であるか、またはその中の一つの元 $d(x)$ の倍式である。

証明

$J\neq\{0\}$ ならば $J$ の中に零でない多項式が存在する。$d(x)$ を $J$ の中で次数が最低のもの（一意とは限らない）とするが、条件 (2) より $d(x)$ の最高次係数を 1 にできる。

こうして任意の $f(x)\in J$ に対して、除法より $q(x),r(x)\in\mathbb{F}[x]$ が存在して

$$f(x) = q(x)d(x) + r(x)$$

を満たし、$r(x)=0$ または $\deg r < \deg d$。条件 (2) より $q(x)d(x)\in J$。条件 (1) より

$$r(x) = f(x) - q(x)d(x) \in J.$$

しかし $\deg r < \deg d$ は $d(x)$ の選び方に矛盾する。したがって $r(x)=0$ となり、任意の $f(x)\in J$ に対して $q(x)\in\mathbb{F}[x]$ が存在して $f(x)=q(x)d(x)$ を満たす。

最高次係数が 1 の別の多項式 $d_1(x)$ が存在して $J=\{h(x)d_1(x) \mid h(x)\in\mathbb{F}[x]\}$ となれば、$d_1(x)\mid d(x)$、$d(x)\mid d_1(x)$ となり、両者の最高次係数はともに 1 であるから $d_1(x)=d(x)$ となり一意性が証明される。

定理31 $f(x)$、$g(x)$ を $\mathbb{F}[x]$ の中の少なくとも一方は零でない二つの多項式とすると、集合

$$J = \{\alpha(x)f(x) + \beta(x)g(x) \mid \alpha(x),\beta(x)\in\mathbb{F}[x]\}$$

は定理30 の条件を満たすから、$d(x)\in J$ が存在して $J=\langle d(x)\rangle$ となる。

明らかに $f(x) = f(x) + 0 \cdot g(x) \in \langle d(x)\rangle$ であるから $f(x)$ は $d(x)$ の倍式で $d(x)\mid f(x)$。同様に $d(x)\mid g(x)$。したがって $d(x)$ は $f(x)$ と $g(x)$ の公因式である。$f(x)$ と $g(x)$ がもう一つの公因式 $d_1(x)$ を持てば、$d(x)\in J$ であるから $\alpha(x),\beta(x)\in\mathbb{F}[x]$ が存在して $d(x)=\alpha(x)f(x)+\beta(x)g(x)$ となり、したがって $d_1(x)\mid d(x)$。すなわち $d(x)$ は $f(x)$ と $g(x)$ の次数最高で最高次係数が 1 の公因式である。

このような公因式を最大公因式と呼び

$$d(x) = (f(x),\, g(x))$$

と記す。$(f(x),g(x))=1$ のとき $f(x)$ と $g(x)$ は互いに素という。

系32（多項式の Bezout 公式） $f(x),g(x)\in\mathbb{F}[x]$ が少なくとも一方は零でないとき、$\alpha(x),\beta(x)\in\mathbb{F}[x]$ が存在して

$$\alpha(x)f(x) + \beta(x)g(x) = (f(x),\, g(x)).$$

特に $f(x),g(x)$ が互いに素のとき、$\alpha(x),\beta(x)\in\mathbb{F}[x]$ が存在して

$$\alpha(x)f(x) + \beta(x)g(x) = 1.$$

以上の結果と概念は $\mathbb{F}[x]$ の中の有限個の零でない多項式の場合に容易に拡張できる。二つの多項式 $f(x)$ と $g(x)$ の最大公因式および Bezout 公式中の $\alpha(x)$ と $\beta(x)$ を具体的に求めるためには、整数の最大公約数を求める手法を参考にして多項式のユークリッドの互除法を確立して解決できる。ここでは詳述しない。

3° 多項式の既約性

整数 $\mathbb{Z}$、あるいは体 $\mathbb{F}$ の係数からなる多項式 $p(x)$ が同様に体 $\mathbb{F}$ の係数からなる二つの非自明な多項式 $p_1(x),\,p_2(x)$ の積

$$p(x) = p_1(x)p_2(x)$$

に分解できるとき、$p(x)$ を整数 $\mathbb{Z}$、あるいは体 $\mathbb{F}$ 上の既約でない多項式（可約多項式）という。そうでない場合を整数 $\mathbb{Z}$、あるいは体 $\mathbb{F}$ 上の既約多項式という。

例7.1 既約か否かは多項式の係数が属する範囲と密接に関係していることに注意しよう。最も単純な例をいくつか挙げる。

$x^2-4$ は $\mathbb{Z}$ 上既約でない：$x^2-4=(x-2)(x+2)$。

$x^2-\dfrac{4}{9}$ のように係数が有理数のときは、$\mathbb{Q}$ 上で $x^2-\dfrac{4}{9}=\left(x-\dfrac{2}{3}\right)\left(x+\dfrac{2}{3}\right)$ と分解できる（整数係数にそろえるなら $9x^2-4=(3x-2)(3x+2)$）。

$x^2-2$ は $\mathbb{Q}$ 上既約だが、$\mathbb{R}$ 上は既約でない：$x^2-2=(x-\sqrt{2})(x+\sqrt{2})$。

$x^2+1$ は $\mathbb{R}$ 上既約だが、$\mathbb{C}$ 上は既約でない：$x^2+1=(x-\mathrm{i})(x+\mathrm{i})$。

これらの例からわかるように、係数が属する範囲が広がるにつれて

$$\mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$$

既約性も変化する。

4° 因式分解

整数が素数の積に分解できるように、任意の体 $\mathbb{F}$ 上の多項式が $\mathbb{F}$ 上の既約多項式の積に分解できることを望む。そのために次の定理がある。

定理33 $\mathbb{F}$ を一つの体とする。

$\mathbb{F}[x]$ の中には無数個の最高次係数が 1 の既約多項式が存在する。
$\mathbb{F}[x]$ の中の任意の多項式 $f(x)$ は既約多項式の積に一意的に分解できる：
$$f(x) = a p_1^{m_1}(x) \cdots p_r^{m_r}(x),$$
ここで $p_1(x),\cdots,p_r(x)$ は $\mathbb{F}[x]$ の中の最高次係数が 1 の既約多項式であり、$m_1,\cdots,m_r$ は重複度を表す。

結論 (1) については、$\mathbb{Q},\mathbb{R},\mathbb{C}$ のような無数個の元を含む体 $\mathbb{F}$ の場合は非常に単純で、任意の $a\in\mathbb{F}$ に対して一次式 $x-a\in\mathbb{F}[x]$ は既約であるから、無数個存在する。その他の状況はここでは論じない。

結論 (2) については、整数の素因数分解の一意性の証明を参考にして、多項式の Bezout の公式から多項式最大公因式の基本性質を導き出すことで証明できる。

練習問題

$n>1$ を整数とする。任意の整数 $m$ に対して $n\mid m$ または $(n,m)=1$ が成立するならば、$n$ は素数でなければならないことを示せ。
$n$ を正整数、$n\geqslant 2$ とする。$\sqrt{n}$ を超えないすべての素数が $n$ を整除できないならば、$n$ は素数でなければならないことを示せ。
正整数 $n>2$ に対して $n$ と $n!$ の間には必ず素数が存在することを証明せよ。
正整数の素因数の標準分解
$$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$
を考える。ここで $p_1,\cdots,p_k$ は二つずつ異なる素数、$\alpha_1,\cdots,\alpha_k$ は対応する素因数の重複度である。$n$ のすべての約数（$n$ と 1 を含む）は次の形の数
$$m = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}$$
であることを示せ。ここで $0\leqslant\beta_1\leqslant\alpha_1$、$0\leqslant\beta_2\leqslant\alpha_2$、$\ldots$、$0\leqslant\beta_k\leqslant\alpha_k$。また $n$ のすべての異なる約数（$n$ と 1 を含む）の個数は $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$ 個であることを示せ。例えば $144=2^4 3^2$ の約数は全部で $5\cdot3=15$ 個あり、具体的には $1,2,4,8,16,3,6,12,24,48,9,18,36,72,144$ である。
自然数を一つの等差（無限）数列とみなすと、定理11 はこの数列に無数多個の素数があることを示している。等差数列
$$4n+3,\quad n=1,2,3,\cdots$$
の中にも無数多個の素数が存在することを証明せよ。

ヒント： 2 より大きい素数は必ず奇数であるから、$4n+1$ または $4n+3$ の形をしている。二つの $4n+1$ の形の数の積もまた $4n+1$ の形の数であることに注意しよう。今 $4n+3$ の形の素数 $p_1,p_2,\cdots,p_r$ しかないと仮定して
$$N = 4(p_1 p_2 \cdots p_r) - 1 = 4(p_1 p_2 \cdots p_r - 1) + 3$$
を考えよ。定理11 の証明と二つの $4n+1$ の形の数の積が $4n+1$ の形の数であるという結論を用いて仮定が誤りであることを導け。
互いに素な二数 $15,7$ に対して整数 $k,l$ を求め $15k+7l=1$ を満たすようにせよ。
合同方程式組を解け：
$$x \equiv 1\pmod{4},\quad x \equiv 2\pmod{5},\quad x \equiv 4\pmod{7}.$$
合同方程式組を解け：
$$5x \equiv 7\pmod{12},\quad 7x \equiv 1\pmod{10}.$$

ヒント： 合同方程式 $ax \equiv b\pmod{m}$ において $(a,m)=1$ のとき、整数 $l,k$ で $al+mk=1$ を満たすものが存在する。したがって $(ax-b)l + mkx = x - bl$、この方程式は $x \equiv bl\pmod{m}$ と同値な形に変形できる。

一方 $m=m_1 m_2$ のとき $(a,m)=1$ は $(a,m_1)=1$、$(a,m_2)=1$ と同値であり、$m\mid(ax-b)$ は $m_1\mid(ax-b)$、$m_2\mid(ax-b)$ と同値であるから、元の方程式は合同方程式組 $ax\equiv b\pmod{m_1}$、$ax\equiv b\pmod{m_2}$ と同値である。

この分析から本問の合同方程式組において
$$5x\equiv 7\pmod{12} \iff x\equiv 2\pmod{3},\; x\equiv 3\pmod{4},$$

$$7x\equiv 1\pmod{10} \iff x\equiv 1\pmod{2},\; x\equiv 3\pmod{5}.$$
$x\equiv 3\pmod{4}$ と $x\equiv 1\pmod{2}$ は $x\equiv 3\pmod{4}$ と同値であることに注意すれば、本問の合同方程式組は次の合同方程式組と同値である：
$$x\equiv 2\pmod{3},\quad x\equiv 3\pmod{4},\quad x\equiv 3\pmod{5}.$$
有理数係数多項式 $\alpha(x)$、$\beta(x)$ を求め
$$x^3\alpha(x) + (1-x)^2\beta(x) = 1$$
を満たすようにせよ。

解答

1. $n$ が素数でない（$n > 1$）とすると、$1 < d < n$ となる約数 $d$ がある。$m = d$ とすると、$n \nmid d$（$0 < d < n$ だから）、また $(n, d) = d > 1$ なので $(n,d) = 1$ でもない。仮定に反するので、$n$ は素数である。

2. $n$ が素数でないとすると、$n = ab$（$1 < a \le b$）と書ける。$a^2 \le ab = n$ だから $a \le \sqrt{n}$。$a$ の素因数 $q$ は $q \le a \le \sqrt{n}$ で、$q \mid a \mid n$ となり、仮定（$\sqrt{n}$ を超えない素数は $n$ を割らない）に反する。よって $n$ は素数である。

3. $N = n! - 1$ を考える。$n \ge 3$ なので $N \ge 5 > 1$ で、素因数 $p$ をもつ。$p \le n$ ならば $p \mid n!$ であり、$p \mid N$ と合わせて $p \mid n! - N = 1$ となり矛盾。よって $p > n$。また $p \le N < n!$。したがって $n < p < n!$ である。

4. $m \mid n$ とすると $n = mk$。素因数分解の一意性より、$m$ に現れる素数は $n$ の素因数 $p_j$ のいずれかで、その指数 $\beta_j$ は $n$ における指数 $\alpha_j$ 以下である（$\beta_j > \alpha_j$ なら $p_j^{\beta_j} \mid n$ となって矛盾）。逆に $0 \le \beta_j \le \alpha_j$ なら $m \mid n$ である。したがって約数は各 $j$ について $\beta_j$ を $\alpha_j + 1$ 通りに選ぶ数に一対一に対応し、個数は $(\alpha_1+1)\cdots(\alpha_k+1)$。

5. $4n+3$ 型の素数が有限個 $p_1, \ldots, p_r$ だけだと仮定し、$N = 4p_1\cdots p_r - 1$ を考える。$N$ は奇数で $N \ge 3$。どの $p_i$ も $N$ を割らない（割れば $p_i \mid 4p_1\cdots p_r - N = 1$）。$N$ の素因数がすべて $4n+1$ 型なら、それらの積である $N$ も $4n+1$ 型になるが、$N = 4(\cdots) + 3$ だから矛盾。よって $N$ は $4n+3$ 型の素因数をもつが、これは $p_1,\ldots,p_r$ のどれとも異なる。仮定に反するので、$4n+3$ 型の素数は無数にある。

6. $15 = 2\cdot 7 + 1$ より $1 = 15 - 2\cdot 7$。よって $k = 1,\ l = -2$。

7. $x = 1 + 4a$ を第 2 式に代入して $4a \equiv 1 \pmod 5$、$a \equiv 4$。$a = 4 + 5b$ とおくと $x = 17 + 20b$。第 3 式より $17 + 20b \equiv 3 + 6b \equiv 4 \pmod 7$、$6b \equiv 1$、$b \equiv 6$。$b = 6 + 7c$ で $x = 137 + 140c$。答えは $x \equiv 137 \pmod{140}$（$137 = 4\cdot 34 + 1 = 5\cdot 27 + 2 = 7\cdot 19 + 4$ で確かめられる）。

8. ヒントの同値な組 $x\equiv 2 \pmod 3$、$x\equiv 3 \pmod 4$、$x\equiv 3 \pmod 5$ を解く。後ろ二つから $x \equiv 3 \pmod{20}$、$x = 3 + 20t$。第 1 式より $3 + 20t \equiv 2t \equiv 2 \pmod 3$、$t \equiv 1$。$t = 1 + 3s$ として $x = 23 + 60s$。答えは $x \equiv 23 \pmod{60}$（$5\cdot 23 = 115 \equiv 7 \pmod{12}$、$7\cdot 23 = 161 \equiv 1 \pmod{10}$）。

9. $\alpha$ の次数は $2$ 未満、$\beta$ の次数は $3$ 未満としてよい。$\alpha = d + ex$、$\beta = a + bx + cx^2$ とおき、$(1-x)^2 = 1 - 2x + x^2$ を掛けて展開する。

$$x^3(d + ex) + (1 - 2x + x^2)(a + bx + cx^2) = a + (b-2a)x + (c - 2b + a)x^2 + (b - 2c + d)x^3 + (c + e)x^4.$$

これが $1$ に等しいので、係数を比べて $a = 1$、$b = 2$、$c = 3$、$d = 2c - b = 4$、$e = -c = -3$。よって

$$\alpha(x) = 4 - 3x,\qquad \beta(x) = 1 + 2x + 3x^2.$$

« 無限実数 »