m, n を整数. g.c.d(m, n) = d, l.c.m(m, n) = l とすると {

m, n を整数. g.c.d(m, n) = d, l.c.m(m, n) = l とすると
{
x ≡ a mod m
x ≡ b mod n
}
を満たす x が存在するための必要十分条件は, a ≡ b mod d であることを示せ. また, 解 が存在すれば, l を法として唯一つであることを示せ,

とはどうやって証明すればよろしいでしょうか？
どなたか詳しい回答をお願いします。

No.2 ベストアンサー 回答者： mtrajcp 回答日時： 2022/05/23 03:37

gcd(m,n)=d

とすると
m=sd
n=td
となる互いに素な整数s,tがある
-----------
x=amodm
x=bmodn
を満たすxが存在するとすると

mj+a=x=nk+b

となる整数j,kがある

mj+a=nk+b
mj-nk=b-a

m=sd
n=td
をmj-nk=b-aに代入すると

b-a=(js-kt)d
だから
b-a=0mod(d)
だから
∴
a=b mod(d)
-----------
s,tは互いに素だから
js+kt=1
となる整数j,kがある
jsd+ktd=d
jm+kn=d

a=b mod(d)
とすると
b-a=Ld
となる整数Lがある
これにjm+kn=dを代入すると
b-a=L(jm+kn)
b-a=Ljm+Lkn
b-Lkn=a+Ljm
だから
x=b-Lkn=a+Ljm
とすると
x=a+Ljmだから
x-a=Ljmだから
∴
x=a mod(m)

x=b-Lknだから
x-b=-Lknだから
∴
x=b mod(n)

No.1 回答者： Tacosan 回答日時： 2022/05/23 01:30

てきとうに検索すれば「誰かの証明」がでてきると思うよ.