算法导论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\)的平凡根。

因此原结论成立。