2010-02-08

離散[ASAP]

Show that the system of congruences x=a1(mod m1) and
x=a2(mod m2) has a solution if and only if gcd(m1,m2) ｜ a1-a2.
於

1 則留言:

  1. 線代離散助教(wynne)2010年2月9日 晚上10:45

    (=>)
    x = k1m1+a1 且 x = k2m2+a2, for some k1,k2
    => a1-a2 = k2m2-k1m1
    => 存在 t 使得 a1-a2 = t*gcd(m1,m2)
    => gcd(m1,m2) | a1-a2

    (<=)
    a1-a2 = k*gcd(m1,m2), for some k
    因為 gcd(m1,m2)=sm1+tm2, for some s,t
    => a1-a2 = k(sm1+tm2)
    => a1-ksm1 = a2+ktm2
    所以取 x = a1-ksm1 = a2+ktm2,
    x = a1 mod m1 且 x = a2 mod m2

    回覆刪除