算法导论31.1 Exercises 答案

31.1-1

\(c=a+b=a\cdot 1+b\)，并且由于\(0< b< a\)，因此根据除法定理\(31.1\)，有\(c \bmod a=b\)。

31.1-2

考虑使用反证法证明。

假设质数是的数量是有限的，只有\(k\)个，分别为\(p_1,p_2,\dots,p_k\)。考虑构造出一个新数\(p=\prod_{i=1}^k p_i + 1\)。

对于所有\(p_i\)，可以发现\(\prod_{j=1}^k p_j\)都是\(p_i\)的倍数。因此\(\left(\prod_{j=1}^kp_j+1\right)\bmod p_i=1\)。也就是说都有\(p_i\nmid p\)。那么我们新构造出了一个质数\(p\)。由此和原来只有\(k\)个质数的结论矛盾。

31.1-3

\(a\mid b,b\mid c\)意味着存在\(k_1,k_2\in \mathbb{Z}\)使得\(b=k_1a,c=k_2b\)，那么说明\(c=(k_1k_2)a\)，因此\(a\mid c\)。

31.1-4

令\(g=\gcd(k,p)\)。那么\(g\mid k,g\mid p\)均成立。由于\(p\)是质数，因此\(g\)的值要么为\(p\)，要么为\(1\)。由于\(k< p\)，那么\(g\)不可能为\(p\)。因此\(g=\gcd(k,p)=1\)。

31.1-5

因为\(\gcd(a,n)=1\)，所以\(\exists x,y,ax+ny=1\)成立。两边同时乘上\(b\)，得到\(bax+bny=b\)。

又因为\(n\mid ab\)，所以\(\exists k,nk=ab\)。因此最终转换成\(nkx+bny=n(kx+by)=b\)。由此可得，\(n\mid b\)。

31.1-6

根据二项式定理，可以写出：

\[(a+b)^p=\sum_{k=0}^p\dbinom{p}{k} a^kb^{p-k}=\dfrac{p!}{k!(p-k)!} a^kb^{p-k}=\dfrac{p\cdot (p-1)!}{k!(p-k)!} a^kb^{p-k}\]

由于组合数是个整数，因此\(k!(p-k)!\mid p\cdot (p-1)!\)。当\(0 < k < p\)时，由于\(k!,(p-k)!\)的所有项都小于\(p\)，并且\(p\)是个质数，因此\(\gcd(p,k!(p-k)!)=1\)。那么根据推论\(31.5\)，有\(k!(p-k)!\mid (p-1)!\)。令\((p-1)!=c\cdot k!(p-k)!\)，那么有\(\dbinom{p}{k}a^kb^{p-k}=cpa^kb^{p-k}\)成立。

因此有：

\[\sum_{k=0}^p\dbinom{p}{k} a^kb^{p-k}\equiv a^p+b^p \pmod p\]

仅仅保留了\(k=0\)和\(k=p\)时的项。

31.1-7

由于\(a\mid b\)，因此\(\exists k\in \mathbb{Z}\)，使得\(b=ka\)成立。

令\(x=q_1b+r_1,r_1=q_2a+r_2\)，其中满足\(0\le r_1< b,0\le r_2< a\)。那么可以得知，\(r_2=(x \bmod b)\bmod a\)。

将两条式子合并，得到\(x=q_1b+q_2a+r_2=q_1ka+q_2a+r_2=(q_1k+q_2)a+r_2\)。

也就是有\(x-r_2=(q_1k+q_2)a\)。因此最终\((x\mod a)\equiv x\equiv r_2\equiv (x \bmod b)\bmod a\)成立。

如果\(x\equiv y\pmod b\)，那么\(\exists k_1\in \mathbb{Z},x-y=k_1b\)成立。那么可以得到\(x-y=(kk_1)a\)成立，因此有\(x\equiv y\pmod a\)。

31.1-8

假设这个整数\(n\)在二进制下是\(\beta\)比特数。

可以发现，所需要测试的\(k\)的值至多为\(\beta\)。因为\(2^{\beta}\)是\(\beta+1\)比特数，比\(n\)还大。

那么将从\(2\)到\(\beta\)遍历\(k\)值，对每个\(k\)进行判断，这个循环需要\(\Theta(\beta)\)次。

从\(1\)和\(n\)之间二分查找整数\(x\)，判断\(x^k\ge n\)。这个二分的过程需要进行\(\Theta(\beta)\)次。

计算\(x^k\)的过程中需要使用乘法和求幂。如果我们朴素地进行求幂，那么在第\(i(1\le i< k)\)次做乘法时，是将一个\(\beta\)位二进制数和\(i\beta\)位二进制数相乘，如果不适用任何方法优化乘法，那么完成一次乘法计算的运行时间为\(\Theta(i\beta ^2)\)，最终完成\(x^k\)的求幂计算需要\(\Theta(\beta^4)\)的计算。如果使用31.6章使用的求幂算法，那么可以将求幂运算优化到\(\Theta(\beta^3\log \beta)\)。

因此，存在一个\(O(\beta^6)\)的算法，完成对\(\beta\)位二进制数\(x\)是否为非平凡幂的测试。

31.1-9

考虑集合\(S:\{ax+by:x,y\in\mathbb{Z}\}\)。

等式 31.6

根据定理31.2，如果交换\(a,b\)的值，那么将\(x,y\)的值也相互交换，那么得到的集合仍然是\(S=\{by+xa:x,y\in \mathbb{Z}\}\)。因此\(\gcd(a,b)=\gcd(b,a)\)。

等式 31.7

根据定理31.2，只需要同时将集合中的\(a,x\)取负，那么得到的集合仍然是\(S=\{-a(-x)+by:x,y\in \mathbb{Z}\}\)。因此\(\gcd(a,b)=\gcd(-a,b)\)。

等式 31.8

根据等式31.7，有\(\gcd(a,b)=\gcd(a,-b)=\gcd(-a,-b)=\gcd(-a,b)\)。可知，\(\gcd(|a|,|b|)\)必定是这个等式中\(4\)个项之一。

等式 31.9

根据定理31.2，令\(y=0\)，那么得到的集合是\(S=\{ax:x\in \mathbb{Z}\}\)。这个集合中最小的正整数是\(|a|\)，因此\(\gcd(a,0)=|a|\)。

等式 31.10

根据定理31.2，令\(y=ka\)，那么得到的集合是\(S=\{(x+ky)a:x,y\in \mathbb{Z}\}\)。只要固定\(y\)，任取\(x\in \mathbb{Z}\)，那么\(x+ky\)就能表示出所有整数。故这个集合中最小的正整数是\(|a|\)，\(\gcd(a,ka)=|a|\)。

31.1-10

考虑通过中间值\(\gcd(a,b,c)\)来证明题目的两个值是相等的。

令\(g=\gcd(a,b,c),h=\gcd(\gcd(a,b),c)\)。

一方面，可以知道有\(h\mid \gcd(a,b),h\mid c\)。

根据\(\gcd\)的性质，从\(h\mid \gcd(a,b)\)可以得到\(h\mid a,h\mid b\)。

由于\(g=\gcd(a,b,c)\)，因此\(h\mid g\)。

另一方面，可以知道\(g\mid a,g\mid b,g\mid c\)。由此可以得到\(g\mid \gcd(a,b)\)。

从而得到\(g\mid h\)。

因此\(h=g\)，完成了对\(\gcd(a,b,c)=\gcd(\gcd(a,b),c)\)的证明。

通过类似的方式，我们可以证明\(\gcd(a,b,c)=\gcd(a,\gcd(b,c))\)。

因此最终得到\(\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))\)。

\(\star\) 31.1-11

需要证明算术基本定理的存在性和唯一性。

存在性

使用反证法证明。

假设存在最小的合数\(n\)，它不能写成一系列的质数乘积。

那么由于\(n\)是合数，因此\(n\)存在两个非平凡因子\(a,b\)满足\(1< a,b< n,ab=n\)。

\(a,b\)都比\(n\)小，那么\(a,b\)可以写成质数的乘积\(a=p_1p_2\dots p_r,b=q_1q_2\dots q_s\)。

最终，\(n\)也可以写成一个质数的乘积序列\(n=ab=p_1p_2\dots p_n q_1q_2\dots q_s\)。与假设矛盾。

因此所有整数都能够写成一系列质数的乘积。

唯一性

使用反证法证明。

假设\(n\)是最小的数，存在两个不同的分解：\(n=p_1p_2\dots p_{r-1}p_r=q_1q_2\dots q_{s-1}q_s\).

那么有\(p_1\mid q_1q_2\dots q_{s-1}q_s\)。

由于\(q_1,q_2,\dots,q_s\)都是质数，根据定理31.7，因此存在一个质数\(q_k(1\le k\le s)\)，使得\(p_1\mid q_k\)。不失一般性，假设\(k=1\)。那么消去\(p_1=q_1\)后，令\(n'=p_2p_3\dots p_{r-1}p_r\)，那么说明\(n'\)也有两个分解：

\(n'=p_2p_3\dots p_{r-1}p_r=q_2q_3\dots q_{s-1} q_s\)

由于\(n'\cdot p_1=n\)，即\(n'< n\)，违背了\(n\)是最小的假设。

因此所有整数的质因数分解都是唯一的。

31.1-12

可以简单地使用长除法进行。假设被除数是\(\beta\)比特数，为\(a=a_{\beta-1}a_{\beta-2}\dots a_{1}a_{0}\)；除数是\(k\)比特数，为\(b=b_{k-1}b_{k-2}\dots b_1 b_0\).

那么这个除法过程将会迭代\(\beta-b\)次。在每一次迭代中，都会做一次比较操作，有时会做一次减法操作。这两种操作的开销都是\(\Theta(\beta)\)。

整个长除法完成后，商和余数都能求出来，最终运行时间为\((\beta-b)\cdot\Theta(\beta)=\Theta(\beta^2)\)。

31.1-13

如果数\(n\)的二进制长度\(\beta\)不是\(2\)的幂，那么可以考虑将最高位补充\(0\)，直到\(\beta\)是\(2\)的幂，由此进行分治。

那么可以将\(n\)写成\(n=h\cdot 2^{\beta/2} + l\)，其中\(h\)是\(n\)高\(\beta/2\)位的结果，\(l\)是\(n\)低\(\beta/2\)位的结果。

通过递归，求解出\(h\)的十进制值\(h'\)和\(l\)的十进制值\(l'\)。那么要重新计算出\(n'\)的十进制值，需要进行一次\(\beta/2\)位数的乘法，以及一次\(\beta\)位数的加法。

那么也就是说，调用一次的结果可以写成：

\(T(\beta)=2T(\beta/2)+M(\beta/2)\)

由于\(M(\beta)=\Omega(\beta)\)，那么考虑如下情况：

• 如果\(\exists k\ge 0,M(\beta)=\Theta(\beta \cdot \lg ^k \beta)\)，那么根据主定理，有\(T(\beta)=\Theta(\beta \lg^{k+1} \beta)=\Theta(M(\beta)\cdot\lg \beta)\)成立。
• 如果\(\exists \epsilon>0,M(\beta)=\Omega(\beta^{1+\epsilon})\)，那么根据主定理，有\(T(\beta)=\Theta(M(\beta))\)。

无论那种情况，都满足\(M(\beta)=O(M(\beta)\cdot \lg \beta)\)。

关于预处理：\(2^{2^0},2^{2^1},\dots,2^{\beta}\)的这些数的十进制预计算。可以知道，这些数一共有\(\lg \beta\)个，每次可以从\(2^{2^{i-1}}\)计算出\(2^{2^i}\)，一次计算需要\(M(\beta/2)\)的时间。因此这部分处理需要\(\Theta(M(\beta)\cdot\lg \beta)\)的时间。

最终合并这两部分时间，得到最终运行时间为\(O(M(\beta)\cdot \lg \beta)\)。

31.1-14

可以发现，在第\(i\)轮中，灯\(j\)被按下开关时当且仅当\(i\mid j\)。

也就是说，灯泡\(j\)的开关被按次数相当于是它的因子个数。

那么如果灯泡被打开，那么意味着它有奇数个因子。

令\(n\)的分解为\(n=\prod_{i=1}^k p_i^{e_i}\)，根据因数个数定理，\(n\)一共有\(\prod_{i=1}^k (e_i+1)\)个因子。

因子个数为奇数，当且仅当对于所有的\(1\le i\le k,e_i\)都是偶数。

因此，只有当\(m\)为平方数时，灯泡\(m\)才会被打开。