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

整数論の問題

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

$p$ を奇素数とし、 $d$ を $p - 1$ の正の約数とする。 $p$ と互いに素な整数 $a$ について、 $a^{t} \equiv 1 (mod p)$ を満たす最小の正の整数 $t$ を $a$ の $p$ を法とする位数といい、位数が $p - 1$ である $a$ を $p$ を法とする原始根という。

$1 \leq a \leq p - 1$ を満たす整数 $a$ のうち $a^{d} \equiv 1 (mod p)$ を満たすもの全体の積を $Q_{d}$ とする。このとき
$Q_{d} \equiv (- 1)^{d + 1} (mod p)$
であることを証明せよ。

ただし、 $p$ を法とする原始根が存在すること、および「 $a$ の位数を $e$ とするとき、正の整数 $t$ について $a^{t} \equiv 1 (mod p)$ となるのは $e ∣ t$ のときであり、かつそのときに限る」ことは用いてよい。

この問題で使うもの

原始根（説明と入口の問題）
法 n を法とする位数（説明と入口の問題）
等差・等比数列の和と Σ（説明と入口の問題）
フェルマーの小定理とオイラーの定理（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

原始根 $g$ を 1 つ固定し、 $1, \dots, p - 1$ をすべて $g^{k}$ （ $0 \leq k \leq p - 2$ ）の形で表して、 $a^{d} \equiv 1$ という条件を指数 $k$ の条件に書きかえましょう。

ヒント 2

$p - 1 = d c$ とおくと、 $g^{k}$ が $a^{d} \equiv 1$ を満たすのは $c ∣ k$ のときに限ります。すると $Q_{d}$ は $g$ の 1 つのべき $g^{c (0 + 1 + \dots + (d - 1))}$ にまとまります。

ヒント 3

$Q_{d} \equiv g^{(p - 1) (d - 1) /2}$ となります。 $d$ が奇数なら $g^{p - 1} \equiv 1$ が使えます。 $d$ が偶数なら、 $g^{(p - 1) /2}$ の 2 乗が $1$ と合同であることから $g^{(p - 1) /2}$ の値を決めましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

原始根 $g$ をとり、 $g^{0}, \dots, g^{p - 2}$ が法 $p$ で $1, \dots, p - 1$ の並べかえであることを、位数の最小性から示している（2 点）
$p - 1 = d c$ として、 $g^{k}$ について $a^{d} \equiv 1$ と $c ∣ k$ が同値であることを示し、条件を満たす $a$ が $g^{c j}$ （ $0 \leq j \leq d - 1$ ）とちょうど対応することを述べている（3 点）
積をまとめて $Q_{d} \equiv g^{(p - 1) (d - 1) /2}$ を導いている（1 点）
$d$ が奇数のとき、 $\frac{d - 1}{2}$ が整数であることと $g^{p - 1} \equiv 1$ から $Q_{d} \equiv 1$ を示している（1 点）
$d$ が偶数のとき、 $p$ が素数であることと位数の最小性から $g^{(p - 1) /2} \equiv - 1$ を示し、 $Q_{d} \equiv (- 1)^{d - 1} = - 1$ を導いて、両方の場合をまとめて結論している（3 点）

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

模範解答を読む

$m = p - 1$ とおき、 $m = d c$ （ $c$ は正の整数）と書く。 $p$ を法とする原始根 $g$ を 1 つとる（存在は用いてよい）。以下、合同式はすべて $p$ を法とする。

ステップ 1（ $1, \dots, p - 1$ を $g$ のべきで表す）. $g^{0}, g^{1}, \dots, g^{m - 1}$ は互いに合同でない。実際、 $0 \leq i < j \leq m - 1$ で $g^{i} \equiv g^{j}$ とすると、 $g$ は $p$ と互いに素なので両辺を $g^{i}$ で割って $g^{j - i} \equiv 1$ となるが、 $0 < j - i < m$ であり、 $g$ の位数が $m$ であることに反する。また $p$ は素数で $p ∤ g$ なので、各 $g^{k}$ は $p$ で割り切れない。よって $g^{0}, \dots, g^{m - 1}$ を $p$ で割った余りは $1, 2, \dots, p - 1$ （ $m$ 個）のちょうど並べかえである。したがって、 $1 \leq a \leq p - 1$ を満たす各 $a$ に対して、 $a \equiv g^{k}$ となる $k \in {0, 1, \dots, m - 1}$ がただ 1 つ存在する。

ステップ 2（ $a^{d} \equiv 1$ を満たす $a$ の決定）. $a \equiv g^{k}$ （ $0 \leq k \leq m - 1$ ）とする。 $a^{d} \equiv g^{k d}$ であり、

$k = 0$ のとき $a \equiv 1$ で、 $a^{d} \equiv 1$ が成り立つ。
$k \geq 1$ のとき $k d$ は正の整数なので、 $g$ の位数が $m$ であることと用いてよい事実から、 $g^{k d} \equiv 1 ⟺ m ∣ k d$ である。 $m = d c$ より $d c ∣ k d ⟺ c ∣ k$ である。

どちらの場合も「 $a^{d} \equiv 1 ⟺ c ∣ k$ 」が成り立つ（ $k = 0$ は $c$ の倍数である）。 $0 \leq k \leq m - 1 = d c - 1$ の範囲の $c$ の倍数は $k = c j$ （ $j = 0, 1, \dots, d - 1$ ）であるから、ステップ 1 の対応により、 $a^{d} \equiv 1$ を満たす $1 \leq a \leq p - 1$ は、 $g^{c j}$ （ $j = 0, 1, \dots, d - 1$ ）とちょうど 1 対 1 に対応する。よって
$Q_{d} \equiv j = 0 \prod d - 1 g^{c j} = g^{c (0 + 1 + \dots + (d - 1))} = g^{\frac{c d ( d - 1 )}{2}} = g^{\frac{m ( d - 1 )}{2}} (1)$
である。

ステップ 3（ $d$ の偶奇による場合分け）.

- $d$ が奇数のとき. $\frac{d - 1}{2}$ は $0$ 以上の整数なので、 $(1)$ と $g^{m} \equiv 1$ （ $g$ の位数が $m$ だから）より
$Q_{d} \equiv (g^{m})^{\frac{d - 1}{2}} \equiv 1 = (- 1)^{d + 1} .$
- $d$ が偶数のとき. $d ∣ m$ より $m$ も偶数である。 $h = g^{m /2}$ とおくと $h^{2} = g^{m} \equiv 1$ なので $p ∣ (h - 1) (h + 1)$ であり、 $p$ は素数なので $h \equiv 1$ または $h \equiv - 1$ である。 $0 < \frac{m}{2} < m$ と $g$ の位数が $m$ であることから $h \neq \equiv 1$ なので、 $h \equiv - 1$ である。 $(1)$ の指数は $\frac{m ( d - 1 )}{2} = \frac{m}{2} \cdot (d - 1)$ と書けるので
$Q_{d} \equiv h^{d - 1} \equiv (- 1)^{d - 1} = (- 1)^{d + 1} .$

結論. いずれの場合も $Q_{d} \equiv (- 1)^{d + 1} (mod p)$ である。 $■$

（補足: $d = p - 1$ のとき $Q_{d} = (p - 1)!$ で、 $p - 1$ は偶数なので $(p - 1)! \equiv - 1$ 、すなわちウィルソンの定理が得られる。例: $p = 13$ , $d = 3$ のとき $a^{3} \equiv 1$ の解は $1, 3, 9$ で、 $1 \cdot 3 \cdot 9 = 27 \equiv 1$ 。 $d = 4$ のとき解は $1, 5, 8, 12$ で、 $1 \cdot 5 \cdot 8 \cdot 12 = 480 = 13 \cdot 37 - 1 \equiv - 1$ 。）

整数論の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題