算法导论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\)阶排列。