算法导论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 f_ix^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\)各选择一个解都能拼凑一个符合条件的解，因此根据乘法原理，原结论成立。