原始根の求め方について

質問

gcd(m, x) =1
ord_m(x) = φ(m)
mが５、７、８、９、１０、１２、１５、２７、３０の時にそれぞれの原始根を求めたいのですがどうやればいいのでしょうか？

回答No.3

Tacosan · ベストアンサー

ん～, それで「無駄が無い」という感じはしない (むしろ「無駄しか無い」ように思える) んだけど, 2^17 や 2^16 などを求めようと考えた理由 (または目的) はなんでしょうか?

とりあえず「φ(27) = 18なので 2^18 ≡ 1(mod 27）を先に計算してなりたつ事を確認」するのが盛大な無駄であることだけは指摘しておきます. 成り立たないことがあるの?

回答No.2

Tacosan

いや, まじめな話として本質的に「すべての可能なパターンを考える」しかないんですよ (たぶん).

しいて言えば「法によっては計算するまでもない」くらい. たとえば, m=5 に対しては計算の必要がまったくないはずです.

補足

なるほど、例えばm = 27 の時なのですが

φ(27) = 18なので
2^18 ≡ 1(mod 27）を先に計算してなりたてつ事を確認してから2^17, 2^16・・・を計算した方が無駄が無くていいですか？

回答No.1

Tacosan

可能なすべての値を調べる.

補足

試そうと思ったらノート三ページくらいの量になりそうなので
もう少し計算量を減らせる方法は有りませんか？