中国剰余定理について。

質問

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

回答No.25

f272 · ベストアンサー

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

回答No.4

f272

「ax+by=1 が整数解を持つ」と「aとbが互いに素」が同値であることは非常に有名な定理です。中国剰余定理の勉強をしているのなら，その前提として既に学んでいるはずですよ。
「ax+by=1 が整数解を持つ」ならば，aとbの公約数をdとするとax+byは必ずdの倍数になります。dが2以上の整数ならax+by=1 になることはないのでd=1です。
逆に「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)を持つことが分かります。

補足

で、必要十分条件については、解決しました。で、本題の法が互いに素でない場合は、どうすれば良いのでしょうか？一部の連立合同方程式にしか求められないのでしょうか？そこをご教授願いたいです。すみません。

回答No.3

f272

n1Nをgcd(m1,m2)倍するとm1N
n2Mをgcd(m1,m2)倍するとm2M
になる。m1とm2はそういうふうに決めたはずだよね。

補足

すみません。n1とn2は互いに素のときn1N+n2M=1を満たす整数N，Mが存在するでなぜ、
n1N ＋n2M＝1という一次不定方程式になるのでしょうか？やはり、ご教授願いたいです。すみません。前の質問は、解決しました。

回答No.2

f272

n1とn2は互いに素のときn1N+n2M=1を満たす整数N，Mが存在する
というのが少し難しいだけで，それ以外は中学生でもわかる程度に詳しく書いているのだが，いったいなにがわからんの？

補足

この両辺をgcd（m1,m2)倍すると、の左辺のところがわかりません。約分でしょうか？ご教授願いたいです。すみません。

回答No.1

f272

(A)
x≡b1 (mod m1)
x≡b2 (mod m2)
を満たすxが存在する
(B)
b1≡b2 (mod gcd(m1,m2))
とする。

(A)⇒(B)
x≡b1 (mod m1)
でm1はgcd(m1,m2)の倍数だから
x≡b1 (mod gcd(m1,m2))
が成り立つ
同様にx≡b2 (mod m2)からx≡b2 (mod gcd(m1,m2))が成り立つ
したがってb1≡b2 (mod gcd(m1,m2))となる。

(B)⇒(A)
m1=n1*gcd(m1,m2)
m2=n2*gcd(m1,m2)
ただしn1とn2は互いに素とおける。
そうするとn1N+n2M=1を満たす整数N，Mが存在するから，子の両辺をgcd(m1,m2)倍したm1N+m2M=gcd(m1,m2)を満たす整数N，Mが存在する。
b1≡b2 (mod gcd(m1,m2))
から
b2-b1はgcd(m1,m2)の倍数であるから，m1N+m2M=gcd(m1,m2)の両辺に適当な数を書ければm1X+m2Y=b2-b1となる。つまり
m1X+m2Y=b2-b1を満たす整数X，Yが存在する。
よってx=m1X+b1=b2-m2Yとすれば，
x≡b1 (mod m1)
x≡b2 (mod m2)
が成り立つ。

補足

m1N+m2M=gcd(m1,m2)を満たす整数N，Mが存在する。
b1≡b2 (mod gcd(m1,m2))
から
b2-b1はgcd(m1,m2)の倍数であるから，m1N+m2M=gcd(m1,m2)の両辺に適当な数を書ければm1X+m2Y=b2-b1となる。つまり
m1X+m2Y=b2-b1を満たす整数X，Yが存在する。
よってx=m1X+b1=b2-m2Yとすれば，
x≡b1 (mod m1)
x≡b2 (mod m2)
が成り立つ。
ここの文章から、もう少し詳しくご教授願いたいです。すみません。