ここから本文です

解決済みのQ&A

原始根の存在定理の証明の中で一部わからない部分があったので、質問させて頂きま...

consatigerさん

原始根の存在定理の証明の中で一部わからない部分があったので、質問させて頂きます。

p:素数
ψ(d)=(1≦X<P, 位数ep(X)=dなるXの個数)
とする。
また、nのすべての約数をd1,d2,d3,…drとする。

このとき、
X^n-1≡0(mod P)
の解の個数は、
ψ(d1)+ψ(d2)+…+ψ(dr)
である。

(位数ep(X)=(e≧1でe^X≡1(mod P)となる最小のべき指数)

質問
なぜ約数をとって見ていくのか?がわかりません。
そして、nの各約数d1,d2,…drがX^n-1≡0(mod P)の解をつくすというのもよくわかりません。

教えてください、よろしくお願いします。

  • 質問日時:
    2008/11/21 21:33:55
  • 解決日時:
    2008/11/22 00:54:53
  • 閲覧数:
    762
    回答数:
    1
  • お礼:
    知恵コイン
    25枚

ベストアンサーに選ばれた回答

langping08さん

X^n - 1≡0 (mod P) を X^n≡1 (mod P) と変形しておきます。
1≦X<P での解の個数 m を求める問題なのですね。

d = 1, 2, 3, ... , n として、
Ψ(d) = {X^n≡1 (mod P) の解のうち、d 乗して "初めて"、
mod P で 1 となる 1≦X<P の数}

とすると、求めたい数 m は、
m = Ψ(1)+Ψ(2)+Ψ(3)+…+Ψ(n) は納得できると思います。
(初めてのベキ指数が異なるので、集合としては分離和です。)

しかしこれは無駄な和を取っていて、d が n の約数でないとき、
Ψ(d) = 0 なのです。以下これを示します。

n÷d = k 余り r (0≦r≦d-1) とします。(n = kd+r)
d が n の約数でないとき 1≦r≦d-1 で、これを仮定します。

現状、X^n≡1 (mod P), X^d≡1 (mod P) です。両方用いると、

X^n≡X^{kd+r}≡(X^d)^k*(X^r)≡X^r≡1 (mod P).

d 乗して 1 (mod P) になるものは、r 乗して 1 (mod P) になるので、
r<d より、d 乗して "初めて" mod P で 1 になるものは存在しません。
(証明終)

だから、d が n の約数の場合だけ数えればよいのです。
n 以下のベキ乗で、いつかは "初めて" が来る(n 乗して初めての
場合も含みます)ので、それらで全てを尽くしています。

原始根の存在は、Ψ(P-1)≧1 を示すのでしょう。

質問した人からのお礼

  • なぜ、nの約数で考えていたのかがよくわかりました。
    ありがとうございました。
  • コメント日時:2008/11/22 00:54:53

グレード

Q&Aをキーワードで検索:

総合Q&Aランキング

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。

知恵コレに追加する

閉じる

知恵コレクションをするID/ニックネームを選択し、「追加する」ボタンを押してください。
※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。

ほかのID/ニックネームで利用登録する