mod計算について

質問

nが素数p,qの積からなる合成数のとき、例えば

a mod n

を考える場合、aはp,qを因数に含みませんよね？

つまり、aとnは互いに素？

合ってますでしょうか？

回答No.2

info22_

>aはp,qを因数に含みませんよね？
間違い。含む場合もあるから、「含まない」とは言えない。
従って
>つまり、aとnは互いに素？
この結論は間違い。aとnは互いに素でない場合もあるから
「aとnは互いに素」とは言えない。

■反例その１
　15 mod 6 = 3
　n=6=2*3(p=2,q=3), a=15=3*5
　nとaは共通因数3(=q)を持つ。
　つまりaとnは互いに素ではない。

■反例その２
　16 mod 6 = 4
　n=2*3(p=2,q=3), a=16=2*2*2*2
　nとaは共通因数2(=p)を持つ。
　つまりaとnは互いに素ではない。

回答No.1

Tacosan

「mod を考える」だけなら, そんな制限に意味は全くありませんが....