この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

整数論の問題

難易度 4大学院入試の標準レベル大学数学整数論

$N = 12096 = 2^{6} \cdot 3^{3} \cdot 7$ とする。 $N$ と互いに素な整数 $a$ に対し、 $a^{k} \equiv 1 (mod N)$ をみたす最小の正の整数 $k$ を法 $N$ における $a$ の位数という。 $N$ と互いに素な整数の法 $N$ における位数としてとりうる値のうち最大のものを $L$ とする。 $1 ≦ a ≦ N - 1$ をみたし $N$ と互いに素な整数 $a$ のうち、法 $N$ における位数がちょうど $L$ であるものの個数を求めよ。

この問題で使うもの

法 n を法とする位数（説明と入口の問題）
中国剰余定理と連立合同式（説明と入口の問題）
オイラー関数の計算（説明と入口の問題）
原始根（説明と入口の問題）
群の位数と元の位数（説明と入口の問題）

この問題を解けるようになるまで（34 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

中国剰余定理で $(Z / N Z)^{\times}$ を法 $64, 27, 7$ の既約剰余類群の直積に分解し、それぞれの群の構造を調べましょう。

ヒント 2

$(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ （ $k ≧ 3$ ）、奇素数べきの法では巡回群になります。最大位数は各成分の位数の最小公倍数です。

ヒント 3

群は $C_{2} \times C_{16} \times C_{18} \times C_{6}$ となり、最大位数は $144 = 2^{4} \cdot 3^{2}$ です。 $2$ 部分と $3$ 部分に分けて、それぞれ最大位数の元の個数を「全体 − 位数が小さい部分群の元」で数えましょう。

答えと解説

答えを見る

1152

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

群の構造: 中国剰余定理より $(Z / N Z)^{\times} ≅ (Z /64 Z)^{\times} \times (Z /27 Z)^{\times} \times (Z /7 Z)^{\times}$ であり、 $a$ の法 $N$ での位数は、法 $64, 27, 7$ それぞれでの位数の最小公倍数である。

$k ≧ 3$ のとき $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ （ $- 1$ と $5$ で生成される）なので、 $(Z /64 Z)^{\times} ≅ C_{2} \times C_{16}$ 。
奇素数のべきを法とすると原始根が存在するので、 $(Z /27 Z)^{\times} ≅ C_{φ (27)} = C_{18}$ 、 $(Z /7 Z)^{\times} ≅ C_{6}$ 。

ここで $C_{n}$ は位数 $n$ の巡回群を表す。よって $G = (Z / N Z)^{\times} ≅ C_{2} \times C_{16} \times C_{18} \times C_{6},$ $∣ G ∣ = 2 \cdot 16 \cdot 18 \cdot 6 = 3456 = φ (N)$ 。

最大位数 $L$ : 元の位数は各成分の位数の最小公倍数なので、最大値は $L = lcm (2, 16, 18, 6) = 144 = 2^{4} \cdot 3^{2}$ であり、実際に各巡回群の生成元をとれば位数 $144$ の元が存在する。

素因数ごとに分解する: $C_{18} ≅ C_{2} \times C_{9}$ 、 $C_{6} ≅ C_{2} \times C_{3}$ より $G ≅ G_{2} (C_{2} \times C_{16} \times C_{2} \times C_{2}) \times G_{3} (C_{9} \times C_{3}) .$ $G$ の元 $g = (g_{2}, g_{3})$ の位数は（ $g_{2}$ の位数） $\times$ （ $g_{3}$ の位数）で、前者は $2$ のべき、後者は $3$ のべきである。よって $g$ の位数が $144 = 16 \cdot 9$ となるのは、 $g_{2}$ の位数が $16$ かつ $g_{3}$ の位数が $9$ のときに限る。

$G_{2}$ （位数 $128$ ）で位数が $8$ の約数となる元は $C_{2} \times C_{8} \times C_{2} \times C_{2}$ に対応し $64$ 個。よって位数がちょうど $16$ の元は $128 - 64 = 64$ 個。
$G_{3}$ （位数 $27$ ）で位数が $3$ の約数となる元は $C_{3} \times C_{3}$ に対応し $9$ 個。よって位数がちょうど $9$ の元は $27 - 9 = 18$ 個。

したがって位数が $L = 144$ の元の個数は $64 \times 18 = 1152.$

$1 ≦ a ≦ N - 1$ で $N$ と互いに素な $a$ は $G$ の元と 1 対 1 に対応するので、答えは $1152$ である。

別解

中国剰余定理より $(Z / N)^{\times} ≅ (Z /64)^{\times} \times (Z /27)^{\times} \times (Z /7)^{\times} ≅ (Z /2 \times Z /16) \times Z /18 \times Z /6$ 。

位数の最大値 $L$ は指数 $lcm (16, 18, 6) = 144 = 2^{4} \cdot 3^{2}$ 。

素因数ごとに分ける。 $Z /18 ≅ Z /2 \times Z /9$ 、 $Z /6 ≅ Z /2 \times Z /3$ より
- $2$ 部分: $Z /2 \times Z /16 \times Z /2 \times Z /2$ 。位数がちょうど $16$ の元は、 $Z /16$ 成分の位数が $16$ （ $φ (16) = 8$ 通り）で、他の $3$ 成分は任意（ $2^{3} = 8$ 通り）: $8 \cdot 8 = 64$ 個。
- $3$ 部分: $Z /9 \times Z /3$ 。位数がちょうど $9$ の元は、 $Z /9$ 成分の位数が $9$ （ $φ (9) = 6$ 通り）、 $Z /3$ 成分は任意（ $3$ 通り）: $18$ 個。

位数がちょうど $144$ の元の個数は積で $64 \cdot 18 = 1152$ 。

検算: 群の位数は $32 \cdot 18 \cdot 6 = 3456 = φ (12096)$ （ $φ = 32 \cdot 18 \cdot 6$ ）で、 $1152$ はその $1/3$ 。位数が $144$ の元の割合として妥当（ $2$ 部分で $64/128 = 1/2$ 、 $3$ 部分で $18/27 = 2/3$ 、積 $1/3$ ）。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題