第七次作业

第七次作业

1.

$$a=8,b=3\\ p=11,q=19,n=pq=209\\ p^{-1}=7,q^{-1}=7\\ y \equiv aqq^{-1}+bpp^{-1}(mod~209)\\ y=179$$

2.

$$M=5*7*9*11=3465\\ M_1=M/m_0=693,M_2=M/m_1=495\\ M_3=M/m_2=385,M_4=M/m_3=315\\ M_1^{-1}=2,M_2^{-1}=3\\ M_3^{-1}=4,M_4^{-1}=86\\ x \equiv a_0M_1M_1^{-1}+a_1M_2M_2^{-1}+a_2M_3M_3^{-1}+a_3M_4M_4^{-1}(mod~3465)\\ x=0$$

3.

$$n=pq=221\\ p=13,q=17\\ 2000^{2019}=(40*50)^{2019}\\ 40 \leftrightarrow (1,6),50 \leftrightarrow (11,16)\\ 所以2000^{2019}=([(1*11)^{2019}~mod~13],[(6*16)^{2019}~mod~17])\\ 由费尔马小定理得：\\ 11^{2019} \equiv 11^{16*126+3} \equiv 11^{3} \equiv 5 (mod~13)\\ 11^{2019} \equiv 11^{12*168+3} \equiv 11^{3} \equiv 5 (mod~17)\\ 可得结果为\phi(2000^{2019})=(5,5)\\ 所以y=5\\$$

4.

$$定义从\mathbb{Z_n}到\mathbb{Z_p} \times \mathbb{Z_q}的映射 \phi\\ 记\mathbb{K}=Ker \phi\\ 对任意(g_1,g_2) \in \mathbb{Z_p} \times \mathbb{Z_q},有 \phi(g_1,g_2)=e当且仅当g_1g_2=e,即g_1=g_2^{-1}。\\ 又因为\mathbb{Z_p} \cap \mathbb{Z_q}={e},因此只能是g_1=g_2=e\\ 所以Ker\phi={(e,e)},映射\phi 是单射。$$

5.

$$定义从 \mathbb{Z_n^{*}}到 \mathbb{Z_p^{*}} \times \mathbb{Z_q^{*}}的映射 \phi为：\\ \phi(x)=([x~mod~p],[x~mod~q])\\ 由中国剩余定理，任意序对中的两个同余式在模n下有唯一解。，因此是满射\\ 证明单射则证明：\\ 对于任意正整数a,b<n,由中国剩余定理得，([a~mod~p],[a~mod~q])=([b~mod~p],[b~mod~q]),所以a=b。满足单射。\\ \phi(a+b)=([(a+b)~mod~p],[(a+b)~mod~q])\\ 因为\mathbb{Z_p^{*}} \times \mathbb{Z_q^{*}}是两个素数乘法群，所以满足\phi(a+b)=([(a+b)~mod~p],[(a+b)~mod~q])=([a~mod~p],[a~mod~q])+([b~mod~p],[b~mod~q])=\phi(a)+\phi(b).\\ \mathbb{Z_n^{*}} \cong \mathbb{Z_p^{*}} \times \mathbb{Z_q^{*}}$$