中国の剰余定理と原始根

質問

アドバイスよろしくおねがいします。

p,ｑを素数としたときに
mod p と mod q　において　原始根になる値gが存在する。それは中国剰余定理からいえる。
という記述があったのですが、原始根と中国剰余定理が結びつきません。

mod p,mod q において原始根ということは
gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…）

で、中国剰余定理は　簡単に言うと　複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。

この二つが結びつきません。
ご教授お願いします

回答No.2

zk43 · ベストアンサー

ちょっと勘違いしました。
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の方も同様。

お礼

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

回答No.1

zk43

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