合同式の問題

質問

(1)3x≡1(mod 5) (2)9x≡6(mod 15) (3)C'a={x|x≡a(mod m)},Ca={x|x≡a(mod n)}とする。nがmの約数とすれば、C'a ( Caであることを示す方法と(1)(2)の合同式を解きたいのですが解法がわかりません。教えてください。

回答No.3

kalgebra · ベストアンサー

追加です。(3)について

nがmの約数ならば、あるkが存在してm=kn
∴　C'a={x|x≡a(mod kn)｝
　　 Ca={x|x≡a(mod n)}　　　　　
だから、C'a ⊆ Ca　となる。

(1)(2)の条件は必要ないですね。

回答No.2

rabbit_cat

(1)(2)は、ユークリッド互除法を利用します。
あるいは、フェルマーの小定理でもいいです。
説明するのが面倒なので、「１次合同式」で検索してみてください。

(3)は、中国人剰余定理を使えばできそうです。

回答No.1

kalgebra

(1)より3x-1≡0(mod 5)
(2)より3(3x-2)≡0(mod 15) ∴3x-2≡0(mod 5)

(1)(2)の合同式を共に満たすxはありません。

(1)から3xは5で割って1余る数
(2)から3xは5で割って2余る数