餘與不足的題目

7｜n + 23｜n + 2 n + 2 = 21kn = 21k – 2 n = 5m + 2 n = 105q + 21k’ – 2 = 105q + 20k’ + (k’ – 2)k’ = 4 n = 105q + 82 1000 < 105q + 82 < 1400 8.73 < q < 12.55 q = 9, 10, 11, 12 n有4個

Chinese Remainder Theorem.

n≡5 (mod 7)= a1 (mod m1)
n≡2 (mod 5)= a2 (mod m2)
n≡1 (mod 3)= a3 (mod m3)

n≡(a1M1y1+a2M2y2+a3M3y3) mod m
m= m1m2m3= 105
M1= m/m1= 15, M2= m/m2= 21, M3= m/m3= 35

M1y1≡ 1(mod m1) => 15y1≡ 1(mod 7) => y1= 1
M2y2≡ 1(mod m2) => 21y2≡ 1(mod 21) => y2= 1
M3y3≡ 1(mod m3) => 35y3≡ 1(mod 35) => y3= -1

n≡ (5*15+2+21-35) mod 105
n≡ 82 mod 105
n= 105k+82, ∀k∈{9, 10, 11, 12}

n={105k+82|k∈Z, 9≤k≤12}
|n|=4

舉例：12除以7=1.....5 差2就整除
由此可知n除以7 餘5也不足2