剰余類環の単元群とオイラー関数

オイラー関数 $φ (n)$ で $(Z / n Z)^{\times}$ の位数を求め、中国剰余定理で $(Z /60 Z)^{\times} ≅ (Z /4)^{\times} \times (Z /3)^{\times} \times (Z /5)^{\times}$ のように巡回群の直積に分けて、元の位数の最大値や位数 $d$ の元の個数を求められる

前提

有限アーベル群の構造と部分群の個数（大学数学代数学）

この技能までの道筋（22 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）

説明

正の整数 $n$ について、 $n$ を法とする剰余類のうち掛け算の逆元をもつものは群 $(Z / n Z)^{\times}$ をなします。この技能では、その位数をオイラー関数 $φ (n)$ で求めます。さらに中国剰余定理で素数べきごとの巡回群の直積に分け、元の位数の最大値や、位数 $d$ の元の個数を数えます。「 $x^{2} \equiv 1 (mod n)$ の解は何個か」「 $a^{k} \equiv 1$ となる最小の $k$ はいくつまで大きくなりうるか」といった合同式の問題を、群の計算に置き換えて解けるようになります。

なぜそうしてよいのか

単元群とオイラー関数. $n \geq 2$ とします。剰余類 $[a]$ が逆元をもつ（ $[a] [x] = [1]$ となる $[x]$ がある）のは、 $g cd (a, n) = 1$ のときに限ります。 $g cd (a, n) = 1$ ならユークリッドの互除法で $a x + n y = 1$ となる整数 $x, y$ が見つかり、 $[a] [x] = [1]$ です。逆に $a x \equiv 1$ なら $a x - 1$ が $n$ の倍数なので、 $a$ と $n$ の公約数は $1$ を割り、 $g cd (a, n) = 1$ となります。こうした $[a]$ 全体は掛け算で閉じていて群をなし、これを $(Z / n Z)^{\times}$ と書きます。その位数、つまり $1 \leq a \leq n$ で $g cd (a, n) = 1$ となる $a$ の個数を $φ (n)$ と書き、オイラー関数と呼びます（ $φ (1) = 1$ と定めます）。素数べき $p^{k}$ では、 $p$ の倍数 $p^{k - 1}$ 個を除けばよいので $φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)$ です。

中国剰余定理で分ける. $g cd (m, m^{'}) = 1$ のとき、 $a mod m m^{'}$ に組 $(a mod m, a mod m^{'})$ を対応させると、これは $Z / m m^{'} Z$ から $Z / m Z \times Z / m^{'} Z$ への全単射になります（中国剰余定理）。しかも和と積を成分ごとに保ちます。「 $a$ が $m m^{'}$ と互いに素」は「 $a$ が $m$ とも $m^{'}$ とも互いに素」と同じなので、単元どうしがちょうど対応します。したがって $(Z / m m^{'} Z)^{\times} ≅ (Z / m Z)^{\times} \times (Z / m^{'} Z)^{\times}$ であり、とくに $φ (m m^{'}) = φ (m) φ (m^{'})$ です。 $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ と素因数分解すれば、 $(Z / n Z)^{\times}$ は各 $(Z / p_{i}^{k_{i}} Z)^{\times}$ の直積になります。

各成分の形（事実として使う）. 奇素数 $p$ では $(Z / p^{k} Z)^{\times}$ は位数 $p^{k - 1} (p - 1)$ の巡回群です（ $p$ を法とする原始根の存在）。 $2$ のべきは例外で、 $(Z /2 Z)^{\times}$ は単位元だけ、 $(Z /4 Z)^{\times} ≅ Z /2$ です。 $k \geq 3$ では $(Z / 2^{k} Z)^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ となり、巡回群ではありません。たとえば法 $8$ では $3^{2}, 5^{2}, 7^{2}$ がどれも $\equiv 1$ です。これで $(Z / n Z)^{\times}$ が巡回群の直積 $Z / m_{1} \times \dots \times Z / m_{s}$ の形に書けるので、あとは前提の技能どおりに数えられます。直積の元 $(g_{1}, \dots, g_{s})$ の位数は、各成分の位数の最小公倍数です。また巡回群 $Z / m$ で $d x = 0$ を満たす元はちょうど $g cd (d, m)$ 個あります。

手順

$n$ を素因数分解する: $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ 。
位数を求める: $φ (n) = \prod_{i} p_{i}^{k_{i} - 1} (p_{i} - 1)$ 。
中国剰余定理で $(Z / n Z)^{\times} ≅ \prod_{i} (Z / p_{i}^{k_{i}} Z)^{\times}$ と分け、各成分を巡回群に置き換える。奇素数 $p$ なら $Z / p^{k - 1} (p - 1)$ 、 $2^{1}$ なら自明な群、 $2^{2}$ なら $Z /2$ 、 $2^{k} (k \geq 3)$ なら $Z /2 \times Z / 2^{k - 2}$ とする。
元の位数の最大値は、並んだ巡回群の位数 $m_{1}, \dots, m_{s}$ の最小公倍数 $lcm (m_{1}, \dots, m_{s})$ である（各成分に生成元をとった元で実現する）。
$x^{d} = 1$ を満たす元の個数を $N (d) = \prod_{j} g cd (d, m_{j})$ で求める。位数がちょうど $d$ の元の個数は、 $N (d)$ から位数が $d$ の真の約数である元の個数を引いて求める（ $d = p^{k}$ なら $N (p^{k}) - N (p^{k - 1})$ ）。

例題

群 $(Z /60 Z)^{\times}$ において、位数がちょうど $2$ である元の個数を求めよ。

例題の解答

手順1. 素因数分解すると $60 = 2^{2} \cdot 3 \cdot 5$ です。

手順2. 位数は $φ (60) = φ (4) φ (3) φ (5) = 2 \cdot 2 \cdot 4 = 16$ です。

手順3. 中国剰余定理で分けて、各成分を巡回群に置き換えます。
$(Z /60 Z)^{\times} ≅ (Z /4 Z)^{\times} \times (Z /3 Z)^{\times} \times (Z /5 Z)^{\times} ≅ Z /2 \times Z /2 \times Z /4$
（位数 $2 \cdot 2 \cdot 4 = 16$ で手順2と一致します。）

手順5. $x^{2} = 1$ を満たす元の個数は
$N (2) = g cd (2, 2) \cdot g cd (2, 2) \cdot g cd (2, 4) = 2 \cdot 2 \cdot 2 = 8$
です。このうち位数が $1$ の元は単位元だけなので、位数がちょうど $2$ の元は $8 - 1 = 7$ 個です。

確認. 実際に $x^{2} \equiv 1 (mod 60)$ の解は $x \equiv 1, 11, 19, 29, 31, 41, 49, 59$ の $8$ 個です（例: $1 1^{2} = 121 = 2 \cdot 60 + 1$ ）。 $1$ を除くと $7$ 個になります。

答え: $7$

よくある誤り

互いに素でない数に分けて $φ$ を掛けてしまう誤り。たとえば $φ (60) = φ (2) φ (30) = 1 \cdot 8 = 8$ としてしまう。正しくは素数べきごとに分けて $φ (60) = φ (4) φ (3) φ (5) = 16$ 。同様に $φ (4) = 2$ であって、 $φ (2)^{2} = 1$ ではない。
$(Z / 2^{k} Z)^{\times}$ （ $k \geq 3$ ）を巡回群と思い込む誤り。たとえば $(Z /8 Z)^{\times} ≅ Z /4$ としてしまう。正しくは $3^{2} \equiv 5^{2} \equiv 7^{2} \equiv 1 (mod 8)$ なので $(Z /8 Z)^{\times} ≅ Z /2 \times Z /2$ で、元の位数の最大値は $2$ 。
元の位数の最大値を、成分の位数の積（＝群の位数）としてしまう誤り。たとえば $(Z /60 Z)^{\times}$ の最大位数を $16$ とする。正しくは $Z /2 \times Z /2 \times Z /4$ より $lcm (2, 2, 4) = 4$ 。
乗法群を加法群と取り違える誤り。たとえば $(Z /5 Z)^{\times} ≅ Z /5$ としてしまう。正しくは単元は $1, 2, 3, 4$ の $4$ 個で、 $2$ が生成元なので $(Z /5 Z)^{\times} ≅ Z /4$ （位数は $p$ ではなく $p - 1$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

剰余環のイデアルと単元の個数（大学数学代数学）
RSA 暗号の鍵生成・暗号化・復号（大学数学暗号理論）
ベビーステップ・ジャイアントステップ法（大学数学暗号理論）
ポーリッヒ・ヘルマン法による離散対数（大学数学暗号理論）
円分体のガロア群と部分体（大学院数学体論・ガロア理論）
Γ₀(N) の指数・尖点・楕円点（大学院数学楕円関数・モジュラー形式）
べきの塔の剰余（大学院数学計算理論・ラムダ計算）
ディリクレ指標の定義と値（大学院数学解析的整数論）
半直積と作用の準同型（大学院数学群論）
有限アーベル群の自己同型群の位数（大学院数学群論）