合同式について

質問

合同式を使いはじめの者です(*_*)

ある数を法とする剰余系について知りたいときに、その他の数を法とする剰余系の情報を用いる方法ってありますか??

たとえば,ある数を18で割った余りを求めたい時に,その数を2や3や9などで割った余りを用いて求める(または絞り込む)ことはできますか??

お願いします(*_*)

回答No.3

WiredLogic · ベストアンサー

#2です。

お礼で

＞かなり絞り込めるんですね!
＞しかし、このように一つ一つ書き上げて確認するしかないのでしょうか?
＞modX のXを変換する式変形とかはないですよね…?

とおっしゃっているところを見ると、

整数の問題をある程度解いてきた、
そしたら、合同式という便利なものがあると解ったので、
その勉強を始めた、

ということではなさそうですね^^

とりあえず、

x ≡ a (mod m), x ≡ b (mod n) が成り立って、
m,nが互いに素ならば、
x ≡ c (mod mn) と、xをmnで割った余りは１つに決まる。

なので、#2の前半で、示した例で１つに決まること、
後半で、３つに絞り込めることは、偶然でなく、必然
だということ、

そこが解っていれば、全部を書き下したのは、
単に説明の便宜のためで、実際には、
例えば、mの方が大きければ、
mで割ってa余るもののうち、nで割ってb余るものを
探せばいいこと、

だけは書いておきます。

#1さんへのお礼で書いておられるようなことは、当然、可能ですが、

やり方自体は#2を参考にできるでしょうが、その上で何をするにせよ、合同式、以前に、倍数・約数・余りなどについての基礎知識が不足している(最低限あれば、お礼のような疑問は湧かないはずなので)と思われますので、

整数の問題や合同式について、基本から説明してある本、
例えば、東京出版の大学への数学の別冊「マスターオブ整数」などで、
そういう基本の事柄を、少なくとも、易しい方の練習問題くらいは解きつつ、理解した上で、
(できれば、全部、と言いたいところですが、直接関連する部分だけであれば、ページ数や問題数は、大した数にはなりません)
チャレンジすることをお勧めします。

お礼

丁寧な回答ありがとうございます(;_;)!

整数問題には系統的な解き方がないみたいなことを先生から聞いていたので、放置していたのですが、
ほんの最近合同式を使えば解けるようになるものもあるんだ、と気づいて勉強しはじめようと思い立ったところなのです(*_*)
やはりまだまだ整数について学ばねば!!

さっそく本屋へ行って探してきます!!

回答No.4

Tacosan

Chinese Reminder Theorem?

回答No.2

WiredLogic

＞たとえば,ある数を18で割った余りを求めたい時に,その数を2や3や9などで割った余りを用いて求める(または絞り込む)ことはできますか??

勿論可能です。

例えば、

x ≡ 0 (mod 2) かつ x ≡ 0 (mod 9) ならば、x ≡ 0 (mod 18)、なのは、すぐ解るでしょうし、

x ≡ 1 (mod 2) かつ x ≡ 3 (mod 9) ならば、
　x ≡ 1 (mod 2) のとき、x ≡ 1,3,5,7,9,11,13,15,17 (mod 18)、
　x ≡ 3 (mod 9) のとき、x ≡ 3,12 (mod 18)だから、
　x ≡ 3 (mod 18) のように求めることができますし、

x ≡ 1 (mod 2) かつ x ≡ 2 (mod 3) のような場合でも、
　上と同じように考えて、x ≡ 5 (mod 6) なので、
　確定はできないものの、x ≡ 5, 11, 17 (mod 18)
　のように、絞り込むことができます。

お礼

ありがとうございます!
かなり絞り込めるんですね!
しかし、このように一つ一つ書き上げて確認するしかないのでしょうか?
modX のXを変換する式変形とかはないですよね…?

回答No.1

alice_44

m を法として合同 ⇔ m を互いに素な数の積に分解し、各因子を法として合同
です。これから派生して、
m を法として合同 ⇒ m の約数を法として合同
となります。下の式では、← 向きの「ならば」は成り立ちません。

お礼

わかりました!

mod24 などを24の因数の剰余系で分割して考える方法があるのか知りたかったのですが、不可能なのですね…