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

整数論の問題

難易度 3期末試験の応用レベル大学数学整数論

$91$ と互いに素な整数 $a$ に対し、 $a^{k} \equiv 1 (mod 91)$ をみたす最小の正の整数 $k$ を、法 $91$ における $a$ の位数という。 $1 ≦ a ≦ 90$ をみたす整数 $a$ のうち、 $91$ と互いに素で、法 $91$ における位数が $12$ であるものの個数を求めよ。

この問題で使うもの

法 n を法とする位数（説明と入口の問題）
原始根（説明と入口の問題）
オイラー関数の計算（説明と入口の問題）
中国剰余定理と連立合同式（説明と入口の問題）
互いに素な法への分解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$91 = 7 \cdot 13$ と分解し、法 $91$ での位数を法 $7$ ・法 $13$ での位数で表しましょう。

ヒント 2

法 $91$ での位数は $lcm (d_{1}, d_{2})$ （ $d_{1}, d_{2}$ はそれぞれ法 $7$ 、法 $13$ での位数）です。また、素数 $p$ を法として位数がちょうど $d$ （ $d ∣ p - 1$ ）の剰余は $φ (d)$ 個あります。

ヒント 3

$lcm (d_{1}, d_{2}) = 12$ となるには $d_{2} \in {4, 12}$ が必要です。それぞれの場合に $d_{1} ∣ 6$ の条件を調べ、 $φ (d_{1}) φ (d_{2})$ を数えましょう。

答えと解説

答えを見る

32

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

解説を読む

$91 = 7 \cdot 13$ である。 $a$ が $91$ と互いに素なとき、法 $7$ での位数を $d_{1}$ 、法 $13$ での位数を $d_{2}$ とすると、
$a^{k} \equiv 1 (mod 91) ⟺ a^{k} \equiv 1 (mod 7) かつ a^{k} \equiv 1 (mod 13) ⟺ d_{1} ∣ k かつ d_{2} ∣ k$
なので、法 $91$ での位数は $lcm (d_{1}, d_{2})$ である。

また中国剰余定理より、 $1 ≦ a ≦ 90$ で $91$ と互いに素な $a$ は、( $a mod 7$ , $a mod 13$ ) の組（それぞれ $0$ でない剰余）と 1 対 1 に対応する。

$7, 13$ は素数なので原始根が存在し、法 $7$ の既約剰余類は位数 $6$ の巡回群、法 $13$ の既約剰余類は位数 $12$ の巡回群をなす。位数 $n$ の巡回群で位数がちょうど $d$ （ $d ∣ n$ ）の元の個数は $φ (d)$ である。よって $d_{1} ∣ 6$ 、 $d_{2} ∣ 12$ で $lcm (d_{1}, d_{2}) = 12$ となる組 $(d_{1}, d_{2})$ について $φ (d_{1}) φ (d_{2})$ を足し合わせればよい。

$lcm (d_{1}, d_{2})$ が $4$ で割り切れるには、 $d_{1} ∣ 6$ は $4$ で割り切れないので $4 ∣ d_{2}$ 、すなわち $d_{2} \in {4, 12}$ が必要である。

$d_{2} = 12$ のとき: $d_{1}$ は $6$ の約数 $1, 2, 3, 6$ のどれでもよい。 $φ (1) + φ (2) + φ (3) + φ (6) = 1 + 1 + 2 + 2 = 6$ 、 $φ (12) = 4$ なので $6 \cdot 4 = 24$ 個。
$d_{2} = 4$ のとき: $lcm$ が $3$ で割り切れるには $3 ∣ d_{1}$ 、すなわち $d_{1} \in {3, 6}$ 。 $φ (3) + φ (6) = 4$ 、 $φ (4) = 2$ なので $4 \cdot 2 = 8$ 個。

以上より、求める個数は $24 + 8 = 32$ である。

別解

$91 = 7 \cdot 13$ なので中国剰余定理より $(Z /91)^{\times} ≅ (Z /7)^{\times} \times (Z /13)^{\times} ≅ Z /6 \times Z /12$ （どちらの群も原始根をもつ巡回群）。位数が $12$ の元の個数を数える。

$G = Z /6 \times Z /12$ で、 $d x = 0$ をみたす元の個数は $g cd (d, 6) g cd (d, 12)$ 。
- $d = 12$ : $6 \cdot 12 = 72$
- $d = 6$ : $6 \cdot 6 = 36$
- $d = 4$ : $2 \cdot 4 = 8$
- $d = 2$ : $2 \cdot 2 = 4$

位数が $12$ の約数である元は $72$ 個。そのうち位数が $6$ の約数（ $d = 6$ ）または $4$ の約数（ $d = 4$ ）である元を除く。両方に入るのは位数が $2$ の約数の元で $4$ 個。よって $72 - (36 + 8 - 4) = 32$ 。

検算（別の方法）: $3$ 成分は $Z /3 \times Z /3$ で位数 $3$ の元が $8$ 個、 $2$ 成分は $Z /2 \times Z /4$ で位数 $4$ の元は $8 - 4 = 4$ 個。 $8 \times 4 = 32$ 。一致する。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題