第一题：
  1. 运用 CRT 求解：

​ x ≡ 8 (mod 11)

​ x ≡ 3 (mod 19) $$ \[\begin{equation} \begin{split} &解：\\& 记a=8,b=3,p=11,q=19,n=pq=209\\& 11*p^{-1}\equiv1(mod\quad19)\\& 19*q^{-1}\equiv1(mod\quad11)\\& 解得：p^{-1}=7，q^{-1}=7\\& x=(8*19*7+3*11*7)mod\quad209=41\\& 则x=41 \end{split} \end{equation}\] $$

第二题：
  1. 运用 CRT 求解：x ≡ 1 (mod 5)

​ x ≡ 2 (mod 7)

​ x≡ 3 (mod 9)

​ x ≡ 4 (mod 11) $$ $$

第三题：
  1. 手动计算 2000^2019 (mod 221)，不允许使用电脑或者其他电子设备。[提示：这是一

道看上去与中国剩余定理无关的计算题。] \[ \begin{equation} \begin{split} &解：\\& 221=13*17\\& 2000↔(11,11)\\& 由费马尔小定理得：\\& 11^{2019}(mod \quad 13)\equiv11^3(mod\quad13)\\& 11^{2019}(mod \quad 17)\equiv11^3(mod\quad17)\\& (11^3(mod\quad13),11^3(mod\quad17))=(5,5)\\& ↔5\\& 2000^{2019}\equiv5(mod \quad221) \end{split} \end{equation} \]

第四题：

  1. 实现一个利用 CRT 求解同余方程的程序（Python 或者 C 语言都可以）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #求乘法逆元
    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = egcd(b % a, a)
            return (g, x - (b // a) * y, y)

    def mod_inverse(a, m):
        g, x, y = egcd(a, m)
        if g == 1:
            return x % m

    result=0
    list1=[]
    M=1

    n=int(input("请输入同余方程组的个数：\n"))
    for i in range(n):
        a=int(input("请输入第{}个方程的余数：".format(i+1)))
        m = int(input("请输入第{}个方程的模数：".format(i + 1)))
        list1.append((a,m))
        #求出总的模数的乘积
        M*=m

    #求解未知数
    for i in range(n):
        bi=M/list1[i][1] #求解bi
        bi_1=mod_inverse(bi,list1[i][1]) #求解bi的乘法逆元
        result+=list1[i][0]*bi*bi_1
    result=result%M
    print("同余方程组的解为：",result)


    image-20231206214436681