cinta HW6

十二月 06, 2023 2005

第十章

  1. 运用 CRT 求解： MATHJAX-SSR-36 MATHJAX-SSR-37

解：易得 MATHJAX-SSR-38

由egcd可得 MATHJAX-SSR-39

由CRT易得，MATHJAX-SSR-40

故x=41

  1. 运用 CRT 求解： MATHJAX-SSR-41 MATHJAX-SSR-42 MATHJAX-SSR-43 MATHJAX-SSR-44

解：易得 MATHJAX-SSR-45 MATHJAX-SSR-46

P=p_1\cdot p_2\cdot p_3\cdot p_4=3465

则对于每一个a_i都有b_i=\frac{P}{p_i}

则： MATHJAX-SSR-49

由egcd可得 MATHJAX-SSR-50

带入运算，易得 MATHJAX-SSR-51

  1. 手动计算 MATHJAX-SSR-52不允许使用电脑或者其他电子设备。[提示：这是一道看上去与中国剩余定理无关的计算题。]

解：由提示猜测，221为合数，容易验证221=13*17

不妨设MATHJAX-SSR-53

有 MATHJAX-SSR-54

可得：

\begin{align*} (40\cdot 50)^{2019}\pmod{13\cdot 17}&= ((1,6)\cdot (11,16))^{2019} \\ &=(1\cdot 11\pmod{13},6\cdot 16\pmod{17})^{2019}\\ &=(11,11)^{2019}\\ &=((-2)^{2019}\pmod{13},(-6)^{2019}\pmod{17})\\ &=((-2)^{3}\pmod{13},(-6)^{3}\pmod{17})\\ &=(5,5) \end{align*}

由egcd易得MATHJAX-SSR-56

不妨设

x \equiv 5 \pmod{13} MATHJAX-SSR-58

易得x=5时成立，则有原式： MATHJAX-SSR-59 成立

  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
    def CRT(a,b,p,q):
        n=p*q
        if p!=q:#虽然这个条件其实是显然的
            p1,q1=egcd(p,q)
        x=(a*q*q1+b*p*p1)%n
        return x

    def egcd(p,q):
        r1,s1,r2,s2=1,0,0,1
        while p!=1 and q!=1:
            if p>q:
                p=p-q
                r1=r1-r2
                s1=s1-s2
            elif p<q:
                q=q-p
                r2=r2-r1
                s2=s2-s1
        if p==1:
            return r1,s1
        elif q==1:
            return r2,s2