• ベストアンサー
※ ChatGPTを利用し、要約された質問です(原文:中国の剰余定理と原始根)

中国剰余定理と原始根について

このQ&Aのポイント
  • 中国剰余定理とは、複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まる定理です。
  • 原始根とは、ある素数pやqに対して、mod pやmod qにおいてgをp-1乗やq-1乗しても1にならない値のことを指します。
  • 中国剰余定理と原始根は、異なる概念ですが、mod pやmod qにおいて原始根になる値gが存在することが中国剰余定理から導かれることがあります。

質問者が選んだベストアンサー

  • ベストアンサー
  • zk43
  • ベストアンサー率53% (253/470)
回答No.2

ちょっと勘違いしました。 mod 3の原始根2は5としてもよいですね。 これだと、mod pでの原始根rと、mod qでの原始根sに対して、 g≡r(mod p)、g≡s(mod q)となるようなgをとればよいと思いま す。(中国式剰余定理から、このようなgは存在する。ただし、pとq を超えることもある。) mod pでは、rはp-1乗して初めて1になるから、gはp-1乗未満では1には ならず、p-1乗して初めて1になる。 mod qの方も同様。

ilnmfay
質問者

お礼

回答ありがとうございました。 よく考えれば g≡r(mod p)、g≡s(mod q) ってすっきりした式で、単純にわかりますね。 勉強になりました。ありがとうございます。

その他の回答 (1)

  • zk43
  • ベストアンサー率53% (253/470)
回答No.1

これは正しいか? 例えば、mod 3での原始根は2のみ。mod 7での原始根は3と5。 共通なものはない。

関連するQ&A

専門家に質問してみよう