CRT's Homeworks

计算机数学

1. Using CRT to solve:
   x ≡ 8 (mod 11)
   x ≡ 3 (mod 19)

   解：令$a=8,b=3;p=11,q=19;n=pq=209$
   记$p_1=p^{-1}(mod\ q);q_1=q^{-1}(mod\ p);$
   由拓展欧几里得算法解得
   $p^{-1}=7,q^{-1}=7;$
   故$x=aq_1q+bp_1p(mod\ n)$
   解得$x=41$

2. Using CRT to solve the system of congruence:
   x ≡ 1 (mod 5)
   x ≡ 2 (mod 7)
   x ≡ 3 (mod 9)
   x ≡ 4 (mod 11)

   解：由题得：
   令：$m_1=5,m_2=7,m_3=9,m_4=11;$
   所以

   $$M=\prod_{i=1}^4m_i=3465$$
   $a_1=1,\ a_2=2,\ a_3=3,\ a_4=4;$
   $b_i=M/m_i;\ b_i^{'}=b_i^{-1}(mod\ m_i)$
   $b_1=693,\ b_2=495,\ b_3=385,\ b_4=315;$
   因为$b_ib_i^{-1}=1(mod\ m_i)$
   得$b_ib_i^{-1}-1=c_cm_i$
   $b_ib_i^{-1}+c_2m_i=1$
   由拓展欧几里得算法解得
   $b_1^{'}=2,\ b_2^{'}=3,\ b_3^{'}=4,\ b_4^{'}=8$
   $$x=\sum_{i=1}^4a_ib_ib_i^{'}(mod\ M)$$
   解得$x=1731$

3. Write a program(C or Python) to solve CRT

 #algorithm of egcd
 def egcd(a,b):
    r0,r1,s0,s1=1,0,0,1
    while b:
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    return r0
#algorithm of CRT
def CRT(a,m):
    M,x=1,0
    b=list()
    b_=list()
    for n in range(len(m)):
        M=M*m[n];
    for i in range(len(m)):
        b.append(M//m[i])
        '''
        compute b_
        because b_[i]*b[i]=1(mod m[i])
        so b[i]*b_[i]-1=c1*m[i]
        than b[i]*b_[i]+c2*m[i]=1
        use egcd to compute the result
        '''
        b_.append(egcd(b[i],m[i]))
        '''
        when the result is a negative number
        let it become a positive number which is a Equivalence class about b_[i]
        '''
        if b_[i]<0:
            b_[i]=b_[i]%m[i]
        x=(a[i]*b[i]*b_[i]+x)%M
    return x
#test the algorithm
l0=[1,2,3,4]
l1=[5,7,9,11]
print(CRT(l0,l1))

1. Complete the proof that it is an isomorphism from $Z_n^* \ to \ \ Z_p^**Z_q^*$
   解：
   ①定义f是从$Z_n^*到Z_p^**Z_q^*的函数$
   $f(x)=([x\ mod \ p],[x\ mod\ q])$

   ②$由于p和q互素，且n=p*q$
   设所有$x,y∈Z_n^* ,x≠y$
   $f(x)=([x\ mod\ p],[x\ mod\ q])$
   $f(y)=([y\ mod\ p],[y\ mod\ q])$
   因为$x≠y,且p与q互素$
   故$x\ mod\ p≠y\ mod\ p$
   且$x\ mod \ q≠y\ mod\ q$
   得$f(x)≠f(y)$
   满足单射条件
   任取$a∈Z_p^**Z_q^*$
   由于$n=p*q且p与q互素$
   故存在$b∈Z^*_p,c∈Z^*_q$
   有$a=b*c$
   故$a∈Z_n^*$
   即$f(a)=([a\ mod\ p],[a\ mod \ q])$
   $f(a)=(b,c)$
   总能找到$a∈Z_n^*与之对应$
   故满足满射条件
   即$f$是一个双射函数

   ③设$a,b∈Z_n^*$
   $a*b=(a*b)\ mod \ n$
   $即a*b=(a*b)\ mod \ p*q$
   $即a*b=(a\ mod \ p)*(b\ mod \ q)$
   $f(a*b)=([(a*b\ mod\ q)mod\ p],(b*a\ mod\ p)mod\ q])$
   $f(a*b)=([(a\ mod\ p)*(b\ mod\ q)mod\ p],[(b\ mod\ q)*(a\ mod\ p)mod\ q]$
   $f(a*b)=f(a)*f(b)$
   $综上所诉，证得Z_n^*与Z_p^**Z_q^*同构$

   1. Let p = 5 and q = 7, n = pq. Please explicitly give the
      correspondece between $Z^∗_n\ and\ Z^∗_p × Z^∗_q.$ Hint: programming is permitted.

#judge prime number
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#generate an array contain numbers from 1 to a-1 which is coprime to a
def array_prime(a):
    l=[]
    for i in range(a):
        if gcd(i,a)==1:
            l.append(i)
    return l
def f(p,q):
    n,i=p*q,0
    l2=[]
    array_prime(n)
    for j in array_prime(n):
        l1=[j,(j%p,j%q)]
        l2.append(l1)
    return l2
print(f(5,7))

result
[[1, (1, 1)], [2, (2, 2)], [3, (3, 3)], [4, (4, 4)], [6, (1, 6)], [8, (3, 1)], [9, (4, 2)], [11, (1, 4)], [12, (2, 5)], [13, (3, 6)], [16, (1, 2)], [17, (2, 3)], [18, (3, 4)], [19, (4, 5)], [22, (2, 1)], [23, (3, 2)], [24, (4, 3)], [26, (1, 5)], [27, (2, 6)], [29, (4, 1)], [31, (1, 3)], [32, (2, 4)], [33, (3, 5)], [34, (4, 6)]]