算法导论31.5 Exercises 答案

31.5-1

令$(a_1,n_1)=(4,5),(a_2,n_2)=(5,11)$。可以知道，$m_1=11,m_2=5$，因此有$m_1^{-1}\bmod n_1=1,m_2^{-1}\bmod n_2=9$。

计算出$c_1=m_1\cdot(m_1^{-1}\bmod n_1) = 11,c_2=m_2\cdot(m_2^{-1}\bmod n_2)=45$。

最终有$a=(c_1a_1+c_2a_2)\bmod(n_1n_2)=49$。

因此，整体解为$49+55k,k\in\mathbb{Z}$。

31.5-2

令$(a_1,n_1)=(1,9),(a_2,n_2)=(2,8),(a_3,n_3)=(3,7)$。可以知道，$m_1=56,m_2=63,m_3=72$，因此有$m_1^{-1}\bmod n_1=5,m_2^{-1}\bmod n_2=7,m_3^{-1}\bmod n_3=4$。

计算出$c_1=m_1\cdot(m_1^{-1}\bmod n_1) = 280,c_2=m_2\cdot(m_2^{-1}\bmod n_2)=441,c_3=m_3\cdot(m_3^{-1}\bmod n_3)=288$。

最终有$a=(c_1a_1+c_2a_2+c_3a_3)\bmod(n_1n_2n_3)=10$。

因此，整体解为$10+504k,k\in\mathbb{Z}$。

31.5-3

由于$\gcd(a,n)=1$，因此$\forall i\in[1,k],\gcd(a,n_i)=1$均成立，令$x$是满足$ax=1\pmod n$的值，即$x=a^{-1}\bmod n$。

那么有$x_i=x\bmod n_i,a_i=a\bmod n_i$。使用等式31.30，由于$ax=1\bmod n$，因此$\forall i\in[1,k],a_ix_i\bmod n_i=1$也成立。

由此，从$x$可以映射到一个关于$x$的向量$(x_1,x_2,\dots,x_k)$。

最终由这个向量通过定理31.27回代即可求出$x$，即$a^{-1}\bmod n$。

31.5-4

令$\displaystyle{f(x)=\sum{i=0}^t f_ix^i}$。通过定理31.27知道，$\displaystyle{\sum{i=0}^t fix^i}=0\pmod n$当且仅当$\displaystyle{\forall j\in[1,k],\sum{i=0}^t f_ix_j^i=0\pmod {n_j}}$均成立。

考虑任意一个$j$，假设方程的$f(x_j)=0\pmod{n_j}$的解的集合为$S_j$。那么从每个$S_j$中选取一个$x_j$，从$(x_1,x_2,\dots,x_k)$映射回去的$x$也是方程$f(x)=0\pmod{n}$的一个解（因为它确保了$f(x)=0\pmod{n_j}$成立）。

从$S_1,S_2,\dots,S_k$各选择一个解都能拼凑一个符合条件的解，因此根据乘法原理，原结论成立。