中国剰余定理について。

質問

以下の画像は、中国剰余定理の互いに素でない場合の説明なのですが、よく分かりません。
なぜこれが、必要十分条件なのかから分かりません。ご教授願いたいです。すみません。

回答No.25

f272 · ベストアンサー

#20での補足「つまり、ia とja をbで割った余りが同じという事でしょうか？」に対して，#21で「最初からずっとそのように言い続けているよね。小学生でもわかる話です。」と言ったよね。

回答No.14

f272

そんな疑問が出るのは，話が全くわかっていないということです。
あなたの思うようにiやjなどの文字を使って，
余りが同じになると仮定する⇒矛盾が起きる⇒余りは同じにならないと結論付ける。
という話ができますか？「分かります」なんて適当なことを言うのはやめた方が良い。

補足

i やjが違うとすると、ia のa とjaのa は同じなのですよね。a と2a が余りが同じになるという事でしょうか？ご教授願いたいです。すみません。

回答No.13

f272

結論としては余りは同じになりません。
余りが同じになると仮定する⇒矛盾が起きる⇒余りは同じにならないと結論付ける。
この話の流れが分かりませんか？

補足

分かります。ですが、別の文字ia やjaをなぜ使い、しかも、なぜ、（ただしi ≦j)しなかったのでしょうか？ご教授願いたいです。すみません。

回答No.12

f272

> なぜ、ia やjaにしたのでしょうか？
ia やjaを考えていけない理由はない。そういうものを考えると，後で都合がよいのです。

補足

a は同じで、i とjが違うと、余りも変わってくると思うのですが。ご教授願いたいです。すみません。ia とja をどのようにすれば、余りが同じになるのでしょうか？ご教授願いたいです。すみません。

回答No.11

f272

> (ただしi ＜j)となるところがわかりません。...そういうふうにiとjを決めただけです。
> それと、0＜jーi＜bかつ...iとjは1以上b-1以下であってi<jなのだから当然です。
> （jーI)a は、bの倍数になることと、...iaもjaもbで割った余りが同じなのだからja-iaはbの倍数になるに決まっています。
> なぜそれで、a とbが互いに素になることに矛盾するのでしょうか？...(j-I)はbの倍数ではないのですからら，(j-I)aがbの倍数であれば，aはbの倍数ということになってしまいます。

補足

では、質問をもう一つしますが、余りが同じなのに、なぜ、ia やjaにしたのでしょうか？ご教授願いたいです。すみません。

回答No.10

f272

あなたが示していた
https://mathtrain.jp/remainder
に証明の概略があるが，それで何がわからんの？

補足

逆に「aとb が互いに素」であるならば，まずa，2a，3a，...，(b-1)aを考えます。これらをbで割った余りが同じものがあればそれをiaとja(ただしi<j)として，0<j-i<bかつ(j-i)aはbの倍数になります。これはaとb が互いに素であることと矛盾しますから，a，2a，3a，...，(b-1)aをbで割った余りはすべて異なることが分かります。そうすると必ずこれらの中にbで割った余りが1であるものが存在します。それをkaとすればka=lb+1です。つまりax+by=1は整数解(x=k,y=-l)を持つことが分かります。
で、質問なのですが、(ただしi ＜j)となるところがわかりません。それと、0＜jーi＜bかつ（jーI)a
は、bの倍数になることと、なぜそれで、a とbが互いに素になることに矛盾するのでしょうか？ご教授願いたいです。すみません。

回答No.9

f272

#1で書いた(B)が成立していれば，#1の最後に書いたように
> よってx=m1X+b1=b2-m2Yとすれば，
> x≡b1 (mod m1)
> x≡b2 (mod m2)
> が成り立つ。
です。これをちょっと変えてxの代わりにxをlcm(m1,m2)で割った余りを考えれば，それがrです。当然，x≡r (mod lcm(m1,m2))ですね。
「あとは、互いに素の時と同じ感じでやればいいんじゃね」については，何をやればいいのかわからん。何を目指して書かれた文章なのかわからないのです。

補足

この後、中国剰余定理の方が互いに素でない場合も成り立つことを、今までの話から、導き出すにはどうすれば良いのかが分かりません。ご教授願いたいです。すみません。

回答No.8

f272

> どうやって使えるように拡張したのかご教授願いたいです。

どういう答えを期待しているんだろう？
「どうやって」にまともに答えると，「頭を使って」ということになるがたぶんそんなことを聞きたいのではないよね。
どのように拡張したかということなら，それこそその記事に詳しく書いてあります。その記事はちゃんと読んだんだよね。

補足

では、x≡b 1（mod m1)、x≡b2 （mod m2)⇔x≡r（LCM（m1,m2))
の時の証明は、どうすれば良いのかが分かりません。あとは、互いに素の時と同じ感じでやればいいんじゃねの所を省略せずにご教授願いたいです。すみません。

回答No.7

f272

> なぜ、拡張をすると法が互いに素でない場合にも使えるのでしょうか？

使えるように拡張したからに決まってます。

補足

どうやって使えるように拡張したのかご教授願いたいです。

回答No.6

f272

その記事に書いてあるよね。
何がわからんの？

補足

中国剰余定理は、法が互いに素である場合にしか使えないのに、なぜ、拡張をすると法が互いに素でない場合にも使えるのでしょうか？ご教授願いたいです。すみません。

回答No.5

f272

> 一部の連立合同方程式にしか求められないのでしょうか？

最初からx≡4 (mod 6)，x≡1 (mod 8)を満たすxは存在しないと言っているよね。そのうえ
(A)
x≡b1 (mod m1)
x≡b2 (mod m2)
を満たすxが存在する
(B)
b1≡b2 (mod gcd(m1,m2))
としたとき(A)と(B)は同値だと言っている。つまり(B)の条件が成立するときに連立合同方程式に解があると言っている。

補足

いえ、続きの、んでこれが成立しているときの続きです。
以下のURLの記事のことです。
https://mathtrain.jp/remainder