整数の整除と合同式 ― 整数論の出発点を固める

整除の定義から出発し，割り算の原理の存在と一意性を厳密に証明する．合同式の定義と基本性質，合同式の演算規則を体系的に扱い，剰余類環$\mathbb{Z}/n\mathbb{Z}$の構成まで解説する教科書スタイルの記事．

2026年2月27日

1 整除の定義

定義 1 (整除).

整数

a, b

（

a \neq = 0

）に対して，

b = a q

を満たす整数

q

が存在するとき，

a

は

b

を整除する（

a

divides

b

）といい，

a ∣ b

と書く．

a

が

b

を整除しないとき

a ∤ b

と書く．

定理 2 (整除の基本性質).

整数

a, b, c

に対して以下が成り立つ．

$a ∣ b$ かつ $b ∣ c$ ならば $a ∣ c$ （推移性）．
$a ∣ b$ かつ $a ∣ c$ ならば任意の整数 $x, y$ に対して $a ∣ (b x + cy)$ （線形結合）．
$a ∣ b$ かつ $b ∣ a$ ならば $a = \pm b$ ．
$a ∣ b$ かつ $b \neq = 0$ ならば $∣ a ∣ \leq ∣ b ∣$ ．

証明.

(1)

b = a q_{1}

，

c = b q_{2}

とすると

c = a (q_{1} q_{2})

より

a ∣ c

．

(2)

b = a q_{1}

，

c = a q_{2}

とすると

b x + cy = a (q_{1} x + q_{2} y)

より

a ∣ (b x + cy)

．

(3)

b = a q_{1}

，

a = b q_{2}

とすると

a = a q_{1} q_{2}

より

q_{1} q_{2} = 1

．

q_{1}, q_{2}

は整数なので

q_{1} = q_{2} = 1

または

q_{1} = q_{2} = - 1

，すなわち

a = \pm b

．

(4)

b = a q

かつ

b \neq = 0

より

q \neq = 0

，

∣ q ∣ \geq 1

なので

∣ b ∣ = ∣ a ∣ \cdot ∣ q ∣ \geq ∣ a ∣

． □

2 割り算の原理

定理 3 (割り算の原理).

任意の整数

a

と正整数

b

に対して，

a = b q + r, 0 \leq r < b

を満たす整数

q

（商）と

r

（剰余）がただ一組存在する．

証明.

存在：集合

S = {a - bk ∣ k \in Z, a - bk \geq 0}

を考える．

k

を十分小さく取れば

a - bk > 0

なので

S \neq = \emptyset

．整列原理により

S

の最小元

r = a - b q

が存在する．

r \geq 0

は

r \in S

より明らか．

r \geq b

と仮定すると

r - b = a - b (q + 1) \geq 0

かつ

r - b < r

となり

r

の最小性に矛盾．よって

0 \leq r < b

．

一意性：

a = b q_{1} + r_{1} = b q_{2} + r_{2}

（

0 \leq r_{1}, r_{2} < b

）とする．

b (q_{1} - q_{2}) = r_{2} - r_{1}

より

b ∣ (r_{2} - r_{1})

．

∣ r_{2} - r_{1} ∣ < b

なので

r_{2} - r_{1} = 0

，したがって

q_{1} = q_{2}

． □

3 合同式の定義と基本性質

定義 4 (合同式).

整数

a, b

と正整数

n

に対して，

n ∣ (a - b)

が成り立つとき，

a

と

b

は

n

を法として合同であるといい，

a \equiv b (mod n)

と書く．

定理 5 (合同式の基本性質).

合同式は同値関係である：任意の整数

a, b, c

と正整数

n

に対して

$a \equiv a (mod n)$ （反射性）．
$a \equiv b (mod n)$ ならば $b \equiv a (mod n)$ （対称性）．
$a \equiv b$ かつ $b \equiv c (mod n)$ ならば $a \equiv c (mod n)$ （推移性）．

証明.

(1)

n ∣ 0

より成立．(2)

n ∣ (a - b)

ならば

n ∣ (b - a)

．(3)

n ∣ (a - b)

かつ

n ∣ (b - c)

ならば

n ∣ ((a - b) + (b - c)) = n ∣ (a - c)

． □

定理 6 (合同式の演算).

a \equiv b (mod n)

かつ

c \equiv d (mod n)

ならば

$a + c \equiv b + d (mod n)$ ．
$a - c \equiv b - d (mod n)$ ．
$a c \equiv b d (mod n)$ ．
任意の非負整数 $k$ に対して $a^{k} \equiv b^{k} (mod n)$ ．

証明.

a - b = n s

，

c - d = n t

とおく．(1)

(a + c) - (b + d) = n (s + t)

．(2) 同様．(3)

a c - b d = a c - b c + b c - b d = c (a - b) + b (c - d) = c \cdot n s + b \cdot n t = n (cs + b t)

．(4) (3) の繰り返し適用による帰納法． □

4 剰余類環 $Z / n Z$

定義 7 (剰余類).

正整数

n

に対して，整数

a

の

n

を法とする剰余類を

\overset{a}{ˉ} = {a + kn ∣ k \in Z}

と定め，

n

個の剰余類の集合を

Z / n Z = {\overset{ˉ}{0}, \overset{ˉ}{1}, \dots, \overline{n - 1}}

と書く．

注意 8.

Z / n Z

上の加法

\overset{a}{ˉ} + \overset{ˉ}{b} = \overline{a + b}

と乗法

\overset{a}{ˉ} \cdot \overset{ˉ}{b} = \overline{ab}

は剰余類の代表元の取り方によらず well-defined であり，

Z / n Z

は可換環をなす．この環が整域であることと

n

が素数であることは同値であり，

n

が素数のとき

Z / n Z

は体をなす．

例 9.

Z /6 Z

において

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{0}

であるから

\overset{ˉ}{2}

と

\overset{ˉ}{3}

は零因子であり，

Z /6 Z

は整域でない．一方

Z /5 Z

では

\overset{ˉ}{1}, \overset{ˉ}{2}, \overset{ˉ}{3}, \overset{ˉ}{4}

がすべて逆元を持ち（

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{1}

，

\overset{ˉ}{4} \cdot \overset{ˉ}{4} = \overset{ˉ}{1}

），体をなす．

整数の整除と合同式 ― 整数論の出発点を固める

1 整除の定義

2 割り算の原理

3 合同式の定義と基本性質

4 剰余類環 $Z / n Z$

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

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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

1 整除の定義

2 割り算の原理

3 合同式の定義と基本性質

4 剰余類環Z/nZ

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

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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

4 剰余類環 $Z / n Z$