算法导论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$个，分别为$p1,p_2,\dots,p_k$。考虑构造出一个新数$p=\prod{i=1}^k p_i + 1$。
对于所有$pi$，可以发现$\prod{j=1}^k pj$都是$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
根据二项式定理，可以写出：
由于组合数是个整数，因此$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}$成立。
因此有：
仅仅保留了$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=p1p_2\dots p{r-1}pr=q_1q_2\dots q{s-1}q_s$.
那么有$p1\mid q_1q_2\dots q{s-1}q_s$。
由于$q1,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’=p2p_3\dots p{r-1}pr=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$才会被打开。