合同式の応用と剰余類の群構造 ― $(\mathbb{Z}/n\mathbb{Z})^*$ の構造

既約剰余類群$(\mathbb{Z}/n\mathbb{Z})^*$の構造を解明する．オイラー関数$\varphi(n)$の計算公式を導出し，フェルマーの小定理，オイラーの定理，ウィルソンの定理を証明する．元の位数と原始根の存在条件を議論する．

Folio公式

2026年2月27日

1 既約剰余類群

定義 1 (既約剰余類群).

正整数

n

に対して，

g cd (a, n) = 1

を満たす剰余類

\overset{a}{ˉ} \in Z / n Z

全体の集合を

(Z / n Z)^{*}

と書く．これは乗法に関して群をなし，既約剰余類群（group of units）という．

証明.

閉性：

g cd (a, n) = 1

かつ

g cd (b, n) = 1

ならば

g cd (ab, n) = 1

（

p ∣ n

かつ

p ∣ ab

ならば

p ∣ a

または

p ∣ b

で矛盾）．結合性：整数の乗法から継承．単位元：

\overset{ˉ}{1}

．逆元：

g cd (a, n) = 1

よりベズーの等式から

a x + n y = 1

，すなわち

a x \equiv 1 (mod n)

，

\overset{x}{ˉ}

が

\overset{a}{ˉ}

の逆元． □

2 オイラー関数

定義 2 (オイラー関数).

正整数

n

に対して

φ (n) = ∣ (Z / n Z)^{*} ∣

，すなわち

1 \leq k \leq n

で

g cd (k, n) = 1

なる

k

の個数をオイラー関数（Euler's totient function）という．

定理 3 (オイラー関数の計算公式).

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

のとき

φ (n) = n p ∣ n \prod (1 - \frac{1}{p}) = i = 1 \prod k p_{i}^{e_{i} - 1} (p_{i} - 1) .

証明.

φ (p^{e}) = p^{e} - p^{e - 1} = p^{e - 1} (p - 1)

を示す．

1

から

p^{e}

までの整数のうち

p

の倍数は

p, 2 p, \dots, p^{e - 1} \cdot p

の

p^{e - 1}

個なので

φ (p^{e}) = p^{e} - p^{e - 1}

．一般の

n

に対しては中国剰余定理（第6回参照）による

(Z / n Z)^{*} ≅ \prod_{i} (Z / p_{i}^{e_{i}} Z)^{*}

から

φ

の乗法性が従い，公式が得られる． □

3 フェルマーの小定理とオイラーの定理

定理 4 (オイラーの定理).

g cd (a, n) = 1

ならば

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

．

証明.

(Z / n Z)^{*} = {\overset{r}{ˉ}_{1}, \overset{r}{ˉ}_{2}, \dots, \overset{r}{ˉ}_{φ (n)}}

とおく．

g cd (a, n) = 1

のとき写像

\overset{r}{ˉ}_{i} \mapsto \overset{a}{ˉ} \overset{r}{ˉ}_{i}

は

(Z / n Z)^{*}

の全単射（

\overset{a}{ˉ}

が可逆だから）である．したがって

\prod_{i} \overset{a}{ˉ} \overset{r}{ˉ}_{i} = \prod_{i} \overset{r}{ˉ}_{i}

，すなわち

\overset{a}{ˉ}^{φ (n)} \prod_{i} \overset{r}{ˉ}_{i} = \prod_{i} \overset{r}{ˉ}_{i}

．

\prod \overset{r}{ˉ}_{i}

は可逆なので両辺を割って

\overset{a}{ˉ}^{φ (n)} = \overset{ˉ}{1}

． □

系 5 (フェルマーの小定理).

素数

p

と

p ∤ a

なる整数

a

に対して

a^{p - 1} \equiv 1 (mod p)

．

証明.

φ (p) = p - 1

をオイラーの定理に適用する． □

4 ウィルソンの定理

定理 6 (ウィルソンの定理).

p

が素数であるための必要十分条件は

(p - 1)! \equiv - 1 (mod p)

．

証明.

(\Rightarrow)

Z / p Z

は体なので

x^{2} \equiv 1 (mod p)

の解は

x \equiv \pm 1

のみ．

(Z / p Z)^{*} = {1, 2, \dots, p - 1}

の元のうち自分自身が逆元であるのは

1

と

p - 1

のみで，残りは

a \neq = a^{- 1}

なる対をなす．よって

(p - 1)! \equiv 1 \cdot (p - 1) \cdot (対の積は各 1) \equiv p - 1 \equiv - 1 (mod p)

．

(\Leftarrow)

n

が合成数のとき

(n - 1)! \equiv - 1 (mod n)

でないことを示す．

n = ab

（

1 < a \leq b < n

）とする．

a \neq = b

ならば

a, b

はともに

(n - 1)!

の因子であり

n ∣ (n - 1)!

となるので

(n - 1)! \equiv 0 \neq \equiv - 1

．

a = b

ならば

n = a^{2}

で

a \geq 2

より

2 a \leq n - 1

なので

a

と

2 a

がともに因子として現れ同様． □

5 元の位数

定義 7 (位数).

g cd (a, n) = 1

のとき，

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

を満たす最小の正整数

k

を

a

の

n

を法とする位数（order）といい，

ord_{n} (a)

と書く．

定理 8.

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

ならば

ord_{n} (a) ∣ m

．特に

ord_{n} (a) ∣ φ (n)

．

証明.

m = ord_{n} (a) \cdot q + r

（

0 \leq r < ord_{n} (a)

）とすると

a^{r} = a^{m} \cdot (a^{- ord_{n} (a)})^{q} \equiv 1

．

r < ord_{n} (a)

と位数の最小性より

r = 0

． □

合同式の応用と剰余類の群構造 ― $(\mathbb{Z}/n\mathbb{Z})^*$ の構造

1 既約剰余類群

2 オイラー関数

3 フェルマーの小定理とオイラーの定理

4 ウィルソンの定理

5 元の位数

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

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

Folio公式の他の記事

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

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

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

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