連立合同式について

質問

N≡1(mod 2)
N≡2(mod 3)
の連立合同式について解を求める１つの方法として、右辺を同じにする形
N≡5(mod 2)
N≡5(mod 3)
を学習しましたが、右辺を等しくするための手順を
(2+3)*1と理解したのですが、それでよいのでしょうか？
例えば３つの連立合同式
N≡2(mod 3)
N≡3(mod 5)
N≡2(mod 7)
の場合、右辺を等しくするための手順を教えてください。よろしくお願いします。

回答No.3

shkwta · ベストアンサー

連立合同式で、右辺を同じにしたものは、それ自体が「解」です。

N≡1(mod 2)
N≡2(mod 3)
これの解は、
N≡5(mod 6)
となります。(6は2×3です）※証明は簡単

N≡2(mod 3)
N≡3(mod 5)
N≡2(mod 7)
これで、もし
N≡E(mod 3)
N≡E(mod 5)
N≡E(mod 7)
となるEが見つかれば、
N≡E(mod 105)
がこの連立合同式の解となります。※これが解であることと、これですべての解を尽くしていることの証明は簡単です。

つまり、「右辺を同じにする」は解法ではなく、解の条件を示すものです。

さて、
法(mod)が互いに素である場合、連立合同式は、互いに独立な（連立でない）合同式に分解することができます。

ア　N≡a (mod K)
イ　N≡b (mod L)
ウ　N≡c (mod M)

上の連立合同式で、K, L, Mは互いに素とします。ここで、

エ　LMp≡1 (mod K)
オ　MKq≡1 (mod L)
カ　KLr≡1 (mod M)

の３つの合同式をそれぞれ解き、p, q, rを求めます。求められたp, q, r を使って、次のS, T, Uを作ります。

S = aLMp
T = bMKq
U = cKLr

すると、エ・オ・カより、次の合同式が成立します。

キ　S≡a (mod K), S≡0 (mod L), S≡0 (mod M)
ク　T≡0 (mod K), T≡b (mod L), T≡0 (mod M)
ケ　U≡0 (mod K), U≡0 (mod L), U≡c (mod M)

E = S + T + U とおくと、キ・ク・ケより
N-E≡0 (mod K), N-E≡0 (mod L), N-E≡0 (mod M)

したがって、
N≡E (mod K)
N≡E (mod L)
N≡E (mod M)
もとの連立合同式アイウの解は、
N≡E (mod KLM)

以上の方法は中国剰余定理と呼ばれています。

式が４つ以上になっても同様です。
N≡a (mod J)
N≡b (mod K)
N≡c (mod L)
N≡d (mod M)
だったら、
KLMp≡1 (mod J)
LMJq≡1 (mod K)
MJKr≡1 (mod L)
JKLs≡1 (mod M)
をそれぞれ解いて、p, q, r, sを求め、
E = aKLMp + bLMJq + cMJKr + dJKLs
を求めます。

お礼

回答ありがとうございます。
参考にしてこれから勉強してみます。
実は、同じ質問を２回投稿してしまい、事務局から削除の連絡メールが届いたので、もう一度投稿してしまいました。（また、叱られるかも）数学は苦手なので、これからもご教授願います。ありがとうございました。

回答No.2

kansai_daisuki

一般的には、何個あっても

N≡a(mod A)
N≡b(mod B)
N≡c(mod C)
...

Ax+a=By+b=Cz+c=...
(この証明文の全体で、x,y,z以外は全て定数。)

ここで、Ax+a=Bx+bについてみてみると、
B≧Aのとき、
Ax=By+γ
〔ここで、γ=(b-a)<Bとする。(b-a)>Bのときは、
(b-a)≡γ(mod B) ここでγ<Bと変形すればよい。〕
だから、
Ax≡αx(mod B) 〔ここで、α<B〕
By+γ≡γ(mod B) 〔ここで、γ<B〕

よって、αx=γとなるように、xを求めればよい。

ここから、Ax+aが求まる。
同様に、By+b,Cz+c,...も求まる。

回答No.1

kansai_daisuki

>N≡2(mod 3)
>N≡3(mod 5)
>N≡2(mod 7)

3x+2=5y+3=7z+2
⇔3x=5y+1=7z
⇔3x=7zより、x=7a,z=3aとおくと、
21a=5y+1
⇔ここで、21a=5y+1
よって、y=4のとき5y+1は21の倍数。

(別解：5y=21a-1とすると、
a=1のとき、21a-1は、5の倍数。)
(別解２:
21a≡a(mod5),5y+1≡1(mod5)より、
a=1,このとき、21a=5y+1より、y=4)

ココから先は、解けますよね。

お礼

回答ありがとうございます。
参考にしてこれから勉強してみます。
実は、同じ質問を２回投稿してしまい、事務局から削除の連絡メールが届いたので、もう一度投稿してしまいました。（また、叱られるかも）数学は苦手なので、これからもご教授願います。ありがとうございました。