プロが教える店舗&オフィスのセキュリティ対策術

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 を法として唯一つであることを示せ,

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

教えて!goo グレード

A 回答 (2件)

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)
    • good
    • 0

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

教えて!goo グレード

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング