算法导论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),fi=g{i-1}-a g_i;$
• $ft=g{t-1}.$

前$t$个约束（因为这足以帮助我们确认出$g$的所有值）足以构造出$gi$中的所有值，因此我们还需要证明$f_t=g{t-1}$才能够说明$g$为所求。由前$t$个约束可以得到

• $g_0=-f_0 a^{-1}$
• $\forall i\in[1,t),gi=(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}gk=-\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}gm=-\sum{i=0}^ma^if_i}$，那么考虑$a^{k+1} g_k$，有

$\begin{aligned}
a^{k+1}gk&=a^{k+1}(g{k-1}-fk) a^{-1}\
&=a^k(g{k-1}-fk)\
&=a^kg{k-1} -a^kfk\
&=-\sum{i=0}^{k-1}a^ifi-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}fia^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$，原结都成立。那么考虑如下情况：

1. $f(x)$不能够写成$(x-a)g(x)$，那么$f(x)$没有零点，原结论成立。
2. $f(x)=(x-a)g(x)$，但是$g(a)=0$，这说明$f(x)$至多只有$t-1$个不同的零点。也就是说，“$f(x)$至多只有$t$个不同的零点”也是正确的，原结论成立。
3. $f(x)=(x-a)g(x)$，并且$g(a)\neq 0$，那么$g(x)$中的所有零点也是$f(x)$的零点，再加上$a$，因此$f(x)$至多只有$t$个不同的零点，原结论成立。

最终，原结论是正确的。