ここから本文です

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

このエントリーをはてなブックマークに追加

質問者

consatigerさん

2008/11/2121:33:55

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

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)の解をつくすというのもよくわかりません。

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

閲覧数:
773
回答数:
1
お礼:
25枚

違反報告

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

langping08さん

2008/11/2122:53:49

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 を示すのでしょう。

質問した人からのコメント

2008/11/22 00:54:53

なぜ、nの約数で考えていたのかがよくわかりました。
ありがとうございました。

ちょい足しを取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル
  • このエントリーをはてなブックマークに追加
簡単にみんなで作るショート動画アプリ Yahoo!Chocotle for Android(無料)

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

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

ID/ニックネームを選択し、「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。

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