2007级信息安全数学基础试卷-B-答案

x ＝21000000 ≡ b1 (mod 7) x ＝21000000 ≡ b2 (mod 11) 因为 Euler 定理给出2? (7) ≡26 ≡1 (mod 7) , 以及1000000 ＝166666 · 6＋4，所以

b1 ≡21000000 ≡(26)166666 · 24 ≡2 (mod 7)。 类似地，因为 2? (11) ≡ 210 ≡1 (mod 11)， 1000000＝100000 · 10，所以

b2 ≡21000000≡(210)1000000 ≡1 (mod 11)。 x ≡ 2 (mod 7) x ≡1 (mod 11) 令 m1 ＝7, m2 ＝11, m ＝ m1 · m2 ＝77 M1 ＝m2 ＝11, M2 ＝m1 ＝7 分别求解同余式

M1? · 11≡1 (mod 7)，M2? · 7≡1 (mod 11) 得到 M1?＝2 , M2?＝8。

2＋8 · 7 ·故 x≡2 · 11 · 1≡100 ≡23(mod 77) 因此，2≡23（mod 77)。