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

整数論の問題

難易度 1教科書の例題レベル大学数学整数論

$41$ と互いに素な整数 $a$ に対し、 $a^{k} \equiv 1 (mod 41)$ をみたす最小の正の整数 $k$ を、 $41$ を法とする $a$ の位数といい、 $ord_{41} (a)$ と書く。 $ord_{41} (3)$ を求めよ。

この問題で使うもの

法 n を法とする位数（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「位数」の技能を使います。フェルマーの小定理から $3^{40} \equiv 1 (mod 41)$ なので、位数は $40$ の約数だけ調べればよいです。

ヒント 2

$3^{4} = 81$ を $41$ で割った余りに注目しましょう。 $81 \equiv - 1 (mod 41)$ となることが鍵です。

ヒント 3

$3^{4} \equiv - 1$ より $3^{8} \equiv 1 (mod 41)$ です。すると位数は $8$ の約数 $1, 2, 4, 8$ のどれかになります。 $3^{1}, 3^{2}, 3^{4}$ が $1$ と合同かどうかを確かめましょう。

答えと解説

答えを見る

8

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

解説を読む

方針：位数は $φ (n)$ の約数である

$41$ は素数なので $φ (41) = 40$ です。 $g cd (3, 41) = 1$ なので、フェルマーの小定理より $3^{40} \equiv 1 (mod 41)$ が成り立ちます。

位数の基本性質「 $a^{k} \equiv 1 ⟺ ord_{n} (a) ∣ k$ 」から、 $ord_{41} (3)$ は $40$ の約数です。 $40$ の約数は
$1, 2, 4, 5, 8, 10, 20, 40$
なので、これらだけを小さい順に調べれば十分です。

累乗を計算する

$3^{1} = 3, 3^{2} = 9, 3^{4} = 81 = 2 \cdot 41 - 1 \equiv - 1 (mod 41)$
したがって
$3^{8} = (3^{4})^{2} \equiv (- 1)^{2} = 1 (mod 41)$
です。

位数を決める

$3^{8} \equiv 1$ なので、ふたたび同じ性質から $ord_{41} (3)$ は $8$ の約数、つまり $1, 2, 4, 8$ のどれかです。ところが
$3^{1} = 3 \neq \equiv 1, 3^{2} = 9 \neq \equiv 1, 3^{4} \equiv - 1 \neq \equiv 1 (mod 41)$
なので、 $1, 2, 4$ はいずれも位数ではありません。

よって $ord_{41} (3) = 8$ です。

別解

$41$ は素数なので、位数は $φ (41) = 40$ の約数である。実際に計算する。
$3^{1} = 3$ , $3^{2} = 9$ , $3^{4} = 81 = 2 \cdot 41 - 1 \equiv - 1 (mod 41)$ 。
よって $3^{8} \equiv (- 1)^{2} = 1 (mod 41)$ となり、位数は $8$ の約数である。
$3^{1} = 3 \neq = 1$ , $3^{2} = 9 \neq = 1$ , $3^{4} \equiv - 1 \neq = 1$ なので、 $1, 2, 4$ は位数にならない。
したがって位数は $8$ である。
検算: $3^{8} = 6561 = 41 \cdot 160 + 1$ （ $41 \cdot 160 = 6560$ ）で、確かに $3^{8} \equiv 1$ 。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題