CINTA_08

发表于 2022-12-04 分类于 CINTA 阅读次数：

CINTA作业七

1、运用$CRT$求解：

$x\equiv 8\ (mod\ 11)$

$x\equiv 3\ (mod\ 19)$

解;

设$a=8,b=3,p=11,q=19,n=209.$

所以求$p,q$的逆元$p^{-1},q^{-1}$.

使用欧几里得算法求得$p^{-1}=7,q^{-1}=7$.

所以$x=aqq^{-1}+bpp^{-1}\ (mod\ 209)=41$

2、运用$CTR$求解：

$x\equiv 1\ (mod\ 5)$

$x\equiv 2\ (mod\ 7)$

$x\equiv 3\ (mod\ 9)$

$x\equiv 4\ (mod\ 11)$

解：

由题得，$M=5*7*9*11=3465$

所以

$b_0=\frac{3465}{5}=693,b_0^{-1}=2$

$b_1=\frac{3465}{7}=495,b_1^{-1}=3$

$b_2=\frac{3465}{9}=385,b_2^{-1}=4$

$b_3=\frac{3465}{11}=315,b_3^{-1}=8$

所以$x=1×693×2+2×495×3+3×385×4+4×315×8(mod\ 3465)=1731$

3、手动计算$2000^{2019}(mod\ 221)$，不允许使用电脑或者其他电子设备。[提示：这是一道看上去与中国剩余定理无关的计算题.]

解：

由题得，$221=13\times 17$,

所以$2000\leftrightarrow (11,11)$,

$(11,11)^{2019}=([11^{2019}\ mod\ 13],[11^{2019}\ mod\ 17])=(11^3,11^3)=(5,5)$

所以结果为：$(5×17×−3+5×13×4)mod\ 221=5$.

4、请使用第一同构定理证明定理10.4中定义的映射$\phi$的单射性。

解：设$\mathbb{Z}_n$到$\mathbb{Z}_p\times\mathbb{Z}_q$的映射$\phi$为:$\phi(x)=([x\ mod\ p],[x\ mod\ q])$,证明$\phi$的单射.

设$\mathbb{K}=ker\phi$,由题可知$\mathbb{Z}_p\times\mathbb{Z}_q$的单位元为$(0,0)$,所以存在唯一的元素$0\in\mathbb{Z_n}$,使得$0\to(0,0)$,所以$\mathbb{K}=ker\phi=\{0\}$

设$\psi:\mathbb{Z}_n\to\mathbb{Z}_n/\mathbb{K}$为标准同态，由第一同态定理可知，存在$\eta:\mathbb{Z}_n/\mathbb{K}\to\phi(\mathbb{Z}_n)$,使得$\phi=\psi\eta$.

因为$\psi:\mathbb{Z}_n\to\mathbb{Z}_n/\mathbb{K}$，$\psi(a)=\psi(b)\to a\mathbb{K}=b\mathbb{K}\to a0=b0$,即$a=b$,所以$\psi$是单射的。

因为$\psi$是单射的，且$\phi=\psi\eta$,

所以$\phi$是单射的.

10、完成定理10.4的证明，即证明$\mathbb{Z}_n^{*}$与同构。

解：

（1）定义$\mathbb{Z}^*_n$到$\mathbb{Z}^*_p\times\mathbb{Z}_q^*$的映射$\phi$为: \[ \phi(x)=([x\ mod\ p],[x\ mod\ q]) \] (2)证明$\phi$是一种双射，即证明$\phi$是满射且单射。根据中国剩余定理，$\phi$显然是满射的。

证$\phi$是单射：任取$a,b\in n$且$a,b< n$,假设$\phi(a)=\phi(b)$，即$([a\ mod\ p],[a\ mod\ q])=[b\ mod\ p],[b\ mod\ q])$，由中国剩余定理可知，$a=b$，所以$\phi$是单射。

(3)证明$\phi$满足群操作：

$(ab)=([(ab) mod p],[(ab) mod q]) $

$=([a\ mod\ p],[a\ mod\ q])\cdot([b\ mod p],[b\ mod\ q])$

$=\phi(a)\cdot\phi(b)$

所以得证。