算法导论31.3 Exercises 答案

31.3-1

群$(\mathbb{Z}_4,+_4),(\mathbb{Z}_5^{\ast},\cdot_5)$：

$\begin{array}{l|llll}
+_4& 0 & 1 & 2 & 3 \
\hline
0 & 0 & 1 & 2 & 3 \
1 & 1 & 2 & 3 & 0 \
2 & 2 & 3 & 0 & 1 \
3 & 3 & 0 & 1 & 2 \
\end{array}
\qquad
\begin{array}{l|llll}
\cdot_5& 1 & 2 & 3 & 4 \
\hline
1 & 1 & 2 & 3 & 4 \
2 & 2 & 4 & 1 & 3 \
3 & 3 & 1 & 4 & 2 \
4 & 4 & 3 & 2 & 1 \
\end{array}$

可以看到，这两个群是同态的：

对于$f(x)=2^x\bmod 5$，其中$x\in \mathbb{Z_4},f(x)\in \mathbb{Z}_5^{\ast}$，都有：$f(a+_4 b)=f(a)\cdot_5 f(b)$。

31.3-2

$\mathbb{Z}_9$有如下子群：

$\begin{aligned}
&\langle0\rangle={0}\
&\langle1\rangle={0,1,2,3,4,5,6,7,8}\
&\langle3\rangle={0,3,6}\
\end{aligned}$

$\mathbb{Z}_{13}^{\ast}$有如下子群：

$\begin{aligned}
&\langle1\rangle={1}\
&\langle2\rangle={1,2,3,4,5,6,7,8,9,10,11,12}\
&\langle3\rangle={1,3,9}\
&\langle4\rangle={1,3,4,9,10,12}\
&\langle5\rangle={1,5,8,12}\
&\langle12\rangle={1,12}\
\end{aligned}$

31.3-3

封闭性：$\forall a,b \in S’,a\oplus b\in S’$，因此满足封闭性。

单位元：假设$a\in S’$，将元素$a$的幂按序列出来，那么有$a,a^2,a^3,\dots,a^{k-1},a,a^{k+1},a^{k+2},\dots$。由于$S’$的大小是有限的，因此总存在一个值$k$使得$a^{k}=a$，那么就找到了一个单位元$a^{k-1}=1$。

结合律：由于$S’$中的元素都是来自于$S$，其运算过程完全一致。因此，由于群$(S,\oplus)$满足结合律，因此$(S’,\oplus)$也满足结合律。

逆元：对于任意$a\in S’$，如果$a^{k+1}=a$，那么它的逆元是$a^{k-1}$，即$a\cdot a^{k-1}=a^k=1$。

31.3-4

$p^e$这个数只有质因子$p$。在$1\sim p^e$种，含有质因子$p$的数的个数为$p^{e-1}$个。

因此有$\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$。

31.3-5

采用反证法来证明。

如果$\exists x,y\in[0,n),x\neq y$，并且有$ax\equiv ay\pmod n$。那么有$a(x-y)\equiv 0\pmod n$，也就是说，$n\mid a(x-y)$。

由于$a\in \mathbb{Z}_n^{\ast}$，因此$\gcd(a,n)=1$，那么$n\mid (x-y)$。只有当$x=y$时，整除才成立，和原假设矛盾。

因此$\forall x,y\in[0,n),x\neq y,f_a(x)\bmod n\neq f_a(y)\bmod n$均成立。由于$f_a(x)\in [0,n)，$因此$f_a(x)=ax\bmod n$是一个$n$阶排列。