素数と算術の基本定理 ― 整数の原子分解

素数の定義と基本性質を定め，素数の無限性のユークリッドによる証明を与える．算術の基本定理（存在と一意性）を厳密に証明し，Miller-Rabin素数判定法やエラトステネスの篩を解説する．

2026年2月27日

1 素数の定義と基本性質

定義 1 (素数).

2

以上の整数

p

が素数（prime）であるとは，

p

の正の約数が

1

と

p

のみであることをいう．素数でない

2

以上の整数を合成数（composite）という．

補題 2 (素数の整除性).

p

を素数とし，

p ∣ ab

ならば

p ∣ a

または

p ∣ b

．

証明.

p ∤ a

と仮定する．

p

は素数なので

g cd (p, a) = 1

．ベズーの等式より

p x + a y = 1

なる整数

x, y

が存在する．両辺に

b

を掛けて

p b x + ab y = b

．

p ∣ p b

かつ

p ∣ ab

より

p ∣ (p b x + ab y) = p ∣ b

． □

系 3.

素数

p

と整数

a_{1}, \dots, a_{n}

に対して

p ∣ a_{1} a_{2} \dots a_{n}

ならば，ある

i

が存在して

p ∣ a_{i}

．

2 素数の無限性

定理 4 (ユークリッド).

素数は無限に多く存在する．

証明.

有限個の素数

p_{1}, p_{2}, \dots, p_{n}

がすべての素数であると仮定する．

N = p_{1} p_{2} \dots p_{n} + 1

を考える．

N \geq 2

なので

N

は少なくとも1つの素因数

p

を持つ．

p

はいずれかの

p_{i}

と一致するはずだが，

p ∣ N

かつ

p ∣ p_{1} \dots p_{n}

より

p ∣ (N - p_{1} \dots p_{n}) = p ∣ 1

．これは

p \geq 2

に矛盾． □

3 算術の基本定理

定理 5 (算術の基本定理).

任意の

2

以上の整数

n

は素数の積として表せる（存在）．さらにその表し方は，因子の順序を除いて一意的である（一意性）．

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}} (p_{1} < p_{2} < \dots < p_{k}, e_{i} \geq 1)

証明.

存在：

n

に関する強帰納法．

n = 2

は素数なので成立．

n > 2

とする．

n

が素数ならば終了．

n

が合成数ならば

n = ab

（

1 < a, b < n

）と書け，帰納法の仮定により

a, b

はそれぞれ素数の積として表せるので

n

もそうである．

一意性：

n = p_{1} p_{2} \dots p_{s} = q_{1} q_{2} \dots q_{t}

（

p_{i}, q_{j}

は素数，

p_{1} \leq \dots \leq p_{s}

，

q_{1} \leq \dots \leq q_{t}

）とする．

s

に関する帰納法で示す．

s = 1

ならば

n = p_{1}

は素数で

t = 1

かつ

q_{1} = p_{1}

．

s \geq 2

とする．

p_{1} ∣ q_{1} q_{2} \dots q_{t}

より，素数の整除性の補題から

p_{1} ∣ q_{j}

なる

j

が存在する．

q_{j}

も素数なので

p_{1} = q_{j}

．両辺を

p_{1}

で割ると

p_{2} \dots p_{s} = q_{1} \dots q_{j - 1} q_{j + 1} \dots q_{t}

となり，帰納法の仮定を適用すれば

s - 1 = t - 1

かつ残りの素因数も（並べ替えを除いて）一致する． □

4 エラトステネスの篩

注意 6.

n

以下の素数をすべて列挙する古典的手法がエラトステネスの篩（sieve of Eratosthenes）である．

2

から

n

までの整数を用意し，

p = 2

から順に

p^{2} \leq n

を満たす素数

p

の倍数

p^{2}, p^{2} + p, \dots

を消去する．残った数がすべて素数である．計算量は

O (n lo g lo g n)

である．

定理 7.

合成数

n

は

n

以下の素因数を持つ．

証明.

n = ab

（

1 < a \leq b < n

）とすると

a^{2} \leq ab = n

より

a \leq n

．

a

の任意の素因数は

a \leq n

以下である． □

5 Miller-Rabin 素数判定法

定義 8.

奇数

n > 2

に対して

n - 1 = 2^{s} d

（

d

は奇数）と書く．整数

a

（

g cd (a, n) = 1

）が

n

に対する強擬素数の証拠であるとは，

a^{d} \equiv 1 (mod n)

または

a^{2^{r} d} \equiv - 1 (mod n)

なる

r \in {0, 1, \dots, s - 1}

が存在することをいう．

定理 9.

n

が素数ならば，

g cd (a, n) = 1

なるすべての

a

は強擬素数の証拠を与える．

n

が合成数ならば，強擬素数の証拠を与える

a

（

1 \leq a \leq n - 1

）は全体の

1/4

以下である．

注意 10.

この定理に基づき，ランダムに

k

個の基底

a

を選んでテストすれば，合成数を素数と誤判定する確率は

4^{- k}

以下となる．

k = 20

で確率は

1 0^{- 12}

以下であり，実用上十分な信頼性を持つ．

素数と算術の基本定理 ― 整数の原子分解

1 素数の定義と基本性質

2 素数の無限性

3 算術の基本定理

4 エラトステネスの篩

5 Miller-Rabin 素数判定法

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ