整数論

質問

ｐを素数、ｇをｐについての原始根とする。
ｋを ｋ｜ｐ－１ を満たす自然数とする。
このときｇ^k の位数を求めよ。

という問題です。
ｋ｜ｐ－１ とは、ｋがｐ－１を割り切る
という意味です。
回答の方針が立たず、行き詰ってしまいました。
どなたかよろしくお願いします。

回答No.1

mickel131 · ベストアンサー

ｇがｐについての原始根、ということは、
ｇはｐ－１乗して初めて１になる、ということ。
すると、
g^1 ,g^2 ,・・・,g^(p-2) はすべて１ではないわけですね。
ｋはｐ－１の約数、と言っていますから、
ｐ－1をｋで割った商は整数ですね。これを、ｍと置くと、
ｐ－1＝ｋｍ　,ｍ＝（ｐ－１）/ｋ
このとき、
（ｇ＾ｋ）＾ｍ＝ｇ＾（ｋｍ）＝ｇ＾（ｐ－１）＝１
つまり、
ｇ＾ｋは　ｍ乗すると１になるわけです。
ｍより小さい自然数ｎで（ｇ＾ｋ）＾ｎ＝１を満たすものはありません。なぜなら、そのようなｎ
が存在するとすれば、
１＝（ｇ＾ｋ）＾ｎ＝ｇ＾（ｋｎ）ですが、
０＜ｋｎ＜ｋｍ＝ｐ－１　なので、
「ｇはｐ－１乗して初めて１になる」ことに矛盾するからです。
したがって、ｇ＾ｋは　ｍ乗して初めて１になります。
よって、ｇ＾ｋの位数は
　ｍ＝（ｐ－１）/ｋ

的はずれ　だったら　ごめんなさい。
大学の代数学はもうほとんど忘れてしまっているので、全く自信ありません。

参考URL：

http://www80.sakura.ne.jp/~aozora/suuron/node2.html

お礼

「的はずれ」だなんてとんでもないです。
本当に分かりやすかったです。
参考URLもとても参考になりました。
本当にありがとうございました。