算法导论31.8 Exercises 答案

31.8-1

如果$n$不是一个奇质数的幂，那么可以将$n$写成$n=p_1^{e_1}p_2^{e_2}\dots p_r^{e_r}$，其中$r\ge 2$。

按照定理31.34，对于$\forall i\in[1,r]$，方程$x=1\pmod {p_i^{e_i}}$都有两个平凡根$-1,1$。

对于方程$x^2=1\pmod n$而言，它最多只有两个平凡根$(-1,1)$。但是按照题目31.5-4的结论，这个方程它含有$2^r>2$个不同的根，因此总存在一组关于所有方程$x_i=1\pmod {p_i^{e_i}}$的根组合$(x_1,x_2,\dots,x_n)$，通过中国剩余定理映射出来的$x$，是方程$x^2=1\pmod n$的非平凡根。

$\star$ 31.8-2

根据欧拉函数函数$\phi$的不完全积性，可以得知$\displaystyle{\phi(n)=\prod_{i=1}^r \phi(p_i)^{e_i}}$。也就是说，$\forall i\in [1,r]$，都有$\phi(e_i^{e_i})\mid \phi(n)$。那么整除所有$\phi(p_i^{e_i})$的最小倍数也应该整除$\phi(n)$，即$\text{lcm}(\phi(p_1^{e_1}),\dots,\phi(p_r^{e_r}))\mid \phi(n)$，那么也就是有$\lambda(n)\mid \phi(n)$。

先通过反证法证明$n$是无平方因子的。假设$n$的某个质因子$p$对应的指数$e$满足$e\ge 2$，那么按照$\phi$的定义，有$p\mid \phi(p^e)$，因为$\phi(p^e)=(p-1)p^{e-1}$。那么按照最小公倍数的定义，因为$\lambda(n)=\text{lcm}(\phi(p_1^{e_1}),\dots,\phi(p_r^{e_r}))$，有$p\mid \lambda(n)$，然而当$\lambda(n)\mid n-1$时，$n$才是Carmichael数，但此时$p\nmid n-1$，因此$\lambda(n)\mid n-1$不可能成立。从而证明了$n$是Carmichael数需要满足$n$是无平方因子的。

接下来使用反证法证明$n$至少有$3$个质因子，如果$n$只有两个质因子$p,q$（即$n=pq$）。那么有$\phi(q)=q-1$，并且由于$n-1=pq-1=p-1\pmod{(q-1)}$，由于$p>1$，因此$q-1\nmid n-1$，这说明$\text{lcm}(p-1,q-1)\nmid n-1$，因此这时$n$不可能是Carmichael数。这说明Carmichael数至少有$3$个质因子。

31.8-3

如果$x^2=1\pmod n$，那么变形后，可以得到$(x+1)(x-1)=0\pmod n$。也就是说，$n\mid(x+1)(x-1)$。

考虑使用反证法来证明：

• 如果$\gcd(x-1,n)=1$或者是$\gcd(x+1,n)=n$，那么有$n\mid(x+1)$，由于$x\in\mathbb{Z}_p^{\ast}$，因此有$x=n-1$，它是平凡的。
• 如果$\gcd(x-1,n)=n$或者是$\gcd(x+1,n)=1$，那么有$n\mid(x-1)$，由于$x\in\mathbb{Z}_p^{\ast}$，因此有$x=1$，它是平凡的。

因此，只要满足了其中一个条件，即$\gcd(x-1,n)$或$\gcd(x+1,n)$是$n$的平凡因子，那么意味着$x$是$x^2=1\pmod n$的平凡根。

因此原结论成立。