離散数学になるのかな？

質問

３日ほど考えたんですが、分からないので質問します。

p を素数とする. 2 以上 p-1 以下の自然数 a と自然数 b について,
a^b ≡ 1 (mod p)　に対して位数が p - 1 となる a を列挙せよ
という問題です。
p = 97 の時 a は３２個あるらしいのですが、
具体的にはどのようなことをするのか教えていただけませんか？

Ｐ・Ｓ
いろいろネット上で調べたのですが、フェルマーの小定理と関係があるんですか？

回答No.1

milkysugar · ベストアンサー

>いろいろネット上で調べたのですが、フェルマーの小定理と関係があるんですか？
関係あり過ぎです．

まずはmod pにおける原始根を1つ探し，それをrとします．原始根とはi < p-1ならr^i ≡ 1(mod p)となるような数，つまり位数p-1の数のことです．（フェルマーの小定理より，p-1乗したら必ず1に合同になります）
物の本には「原始根表」「mod pでの指数表」なるものが載っているのでそれを参照．

するとr^1，r^2，…，r^(p-1)は（mod pで）相異なる数になります．あとはr^iの位数を考えればいいのですが，iとp-1の最大公約数をdとした時，位数は(p-1)/dであることが簡単にわかります．
つまりiがp-1と互いに素であることが，r^iが位数p-1になることの条件となります．

以上の話にp=97を代入すればOK．原始根の個数は「96以下の自然数で96と互いに素なものの数」ですから32個なのです．

お礼

数学の苦手な私に、これほどまでに丁寧に説明していただき、ありがとうございます。
実はｐを入力した時に、そのａとａの個数を表示するＣ言語のプログラムを
作っていまして、おかげさまで完成することができました。

＞関係あり過ぎです．
フェルマーの小定理をつい最近知ったばかりで自信が持てませんでしたが、
だいたいは理解できたみたいです。ありがとうございます。

回答No.2

nubou

この定理の親戚がＲＳＡ暗号に使われています
最初にはやった非対称暗号です
今でも広く普及しています

お礼

前述にもありますように、Ｃ言語のプログラムを作っていまして、
そのような話は講義中、具体的な内容は説明されてませんが、紹介はされました。
暗号化理論の基礎になるものだと認識しております。
回答ありがとうございました。