算法导论31.4 Exercises 答案
31.4-1
第一步通过求解\(35x+50y=\gcd(35,50)\)得到一组解\((3,-2)\)，那么计算出来的\(x_0=x\cdot \dfrac{b}{d}=6\)。
随后计算\(\left(x_0+i\cdot\dfrac{n}{d}\right)\)，对于\(i=\{0,1,2,3,4\}\)，得到解的集合为\(\{6,16,26,36,46\}\)。
31.4-2
也就是说，从方程\(a(x-y)=0\pmod n\)推导出\(x-y=0\pmod n\)。令\(z=(x-y)\bmod p\)，那么按照推论31.25，由于\(d=\gcd(a,n)=1\)，因此方程\(az=0\pmod p\)有唯一解，即\(z=0\)，从而满足\(x=y\pmod n\)。否则，\(z\)将有多个解，这将不再保证\(z=0\pmod n\)成立。
如果\(a=2,n=6\)，那么令\(x=1,y=4\)，虽然有\(ax=ay=2\pmod n\)，但是不满足\(x=y\pmod n\)。
31.4-3
仍然可以正常工作，而且\(x_0\)是这些解中最小的一个。
考虑这种情况下的\(x_0\)，那么存在整数\(q\)，使得\(x_0=\dfrac{x'b}{d}-\dfrac{qn}{d}\)成立，我们只需要验证\(x_0\)是否为\(ax=b\pmod n\)的解即可。
使用定理31.24类似的证明步骤，那么有
\(\begin{aligned} ax_0&=a(x'b/d-qn/d)\pmod n\\ &=(b-aqn/d)\pmod n\\ &=(b-(a/d)qn)\pmod n\\ &=b\pmod n \end{aligned}\)
因此这种情况下，\(x_0\)仍然是原方程的解。后面的\(x_i\)值正确性论证方式和原结论一致，因此原结论是正确的。
\(\star\) 31.4-4
令\(\displaystyle{f(x)=\sum_{i=0}^t f_ix^i,g(x)=\sum_{i=0}^{t-1} g_ix^i}\)。
如果\(a=0\)，那么简单地对\(f(x)\)提取一个因子\(x\)即可得到\(g(x)\)。
如果\(a\neq 0\)，那么对于\(f\)中的每个系数\(f_i\)，考虑使用\(g_i\)来表示：
- \(f_0=-a g_0;\)
- \(\forall i\in[1,t),f_i=g_{i-1}-a g_i;\)
- \(f_t=g_{t-1}.\)
前\(t\)个约束（因为这足以帮助我们确认出\(g\)的所有值）足以构造出\(g_i\)中的所有值，因此我们还需要证明\(f_t=g_{t-1}\)才能够说明\(g\)为所求。由前\(t\)个约束可以得到
- \(g_0=-f_0 a^{-1}\)
- \(\forall i\in[1,t),g_i=(g_{i-1}-f_i) a^{-1}\)
由于\(p\)是质数，因此\(\gcd(a,p)=1\)，因此\(a\)在\(\mathbb{Z}_p^{\ast}\)上的逆元\(a^{-1}\)必定存在。
我们首先使用归纳法证明：\(\displaystyle{\forall t\in[0,t),a^{k+1}g_k=-\sum_{i=0}^k}f_ia^i\)。
当\(k=0\)时，\(ag_0=-f_0\)，原结论成立。
当\(k>0\)时，假设对于\(m=0,1,\dots,k-1\)，都满足\(\displaystyle{a^{m+1}g_m=-\sum_{i=0}^ma^if_i}\)，那么考虑\(a^{k+1} g_k\)，有
\(\begin{aligned} a^{k+1}g_k&=a^{k+1}(g_{k-1}-f_k) a^{-1}\\ &=a^k(g_{k-1}-f_k)\\ &=a^kg_{k-1} -a^kf_k\\ &=-\sum_{i=0}^{k-1}a^if_i-a^{k}f_k\\ &=-\sum_{i=0}^{k}a^if_i \end{aligned}\)
因此原结论成立。
此外，由于\(\displaystyle{f(a)=\sum_{i=0}^{t-1}f_ia^i+f_ta^t}\)，并且\(f(a)=0\)，因此有\(\displaystyle{f_ta^t=-\sum_{i=0}^{t-1}f_ia^i=g_{t-1}a^t}\)。最终得到\(g_{t-1}=f_t\)。
因此，根据多项式\(f\)以及其零点\(a\)，我们构造出了一个多项式\(g\)使得\(f(x)=(x-a)g(x)\)。
对于后面的那个结论，使用归纳法来证明。
当\(f(x)\)的度数\(t=1\)时，有\(x=-a \pmod p\)，原结论成立。
当\(f(x)\)的度数大于\(1\)时，假设对于\(t'=1,2,3,\dots,t-1\)，原结都成立。那么考虑如下情况：
- \(f(x)\)不能够写成\((x-a)g(x)\)，那么\(f(x)\)没有零点，原结论成立。
- \(f(x)=(x-a)g(x)\)，但是\(g(a)=0\)，这说明\(f(x)\)至多只有\(t-1\)个不同的零点。也就是说，“\(f(x)\)至多只有\(t\)个不同的零点”也是正确的，原结论成立。
- \(f(x)=(x-a)g(x)\)，并且\(g(a)\neq 0\)，那么\(g(x)\)中的所有零点也是\(f(x)\)的零点，再加上\(a\)，因此\(f(x)\)至多只有\(t\)个不同的零点，原结论成立。
最终，原结论是正确的。