数论基础阅读笔记与习题解答之二:欧几里德算法

《数论基础》第二章首先介绍了如何使用欧几里德算法计算最大公约数,在此基础上介绍了质数与质因数分解的概念以及线性丢番图方程。各节习题解答如下:

2.1 使用减法求解最大公约数

2.1.1 考虑到斐波那契序列的每项均为前两项之和,则有:

$$ gcd(F_n,F_{n-1})=gcd(F_{n-1},F_n-F_{n-1})=gcd(F_{n-1},F_{n-2}) $$

即每相邻两项的最大公约数相等,如此递推到数列前两项的最大公约数\(gcd(F_2,F_1)=1\),所以斐波那契序列中每相邻两项的最大公约数都是\(1\)

2.1.2 同理,每相邻两项的最大公约数等于第一项与第二项的最大公约数\(gcd(3,1)=1\)

2.1.3 假设\(n=ab(b>a)\),则\(a,b\)都为\(n\)的因子。\(a,b\)显然不能都大于\(\sqrt{n}\),否则\(ab>n\)与我们之前的假设矛盾,所以必须存在\(a\le\sqrt{n}\)

2.1.4 对于一个\(k\)位的二进制数,当其所有位数均是\(1\)最大,此时这个二进制数为\(2^k-1\)。又因为小于等于\(\sqrt{n}\)的数字最多有\(\sqrt{n}\)个,则有:

$$ \sqrt{n}=\sqrt{2^k-1}<\sqrt{2^k}=2^{k/2} $$

所以小于\(\sqrt{n}\)的数字最多有\(2^{k/2}\)个,因为上述不等式取不到等号,所以不会有恰好有\(2^{k/2}\)个。

2.1.5 假设\(gcd(u,v)=g\ne1\),则有:

$$ \begin{aligned} x & =2uv=2( gu')( gv') =2g^{2} u'v'\\ y & =u^{2} -v^{2} =( gu')^{2} -( gv')^{2} =g^{2}\left( u^{\prime 2} -v^{\prime 2}\right) \end{aligned} $$

则有\(gcd(x,y)=g^2\ne1\),不是一个本原勾股数组。

2.2 使用带余除法计算最大公约数

2.2.1 使用同样的方法,可计算连分数展开如下:

$$ \begin{aligned} \frac{34}{19} & =1+\frac{15}{19} =1+\frac{1}{19/15}\\ \frac{19}{15} & =1+\frac{4}{15} =1+\frac{1}{15/4}\\ \frac{15}{4} & =3+\frac{3}{4} =3+\frac{1}{4/3}\\ \frac{4}{3} & =1+\frac{1}{3} =1+\frac{1}{3} \end{aligned} $$

2.2.2 和上题完全一样,这里从略

2.2.3 将上面两题的连分数展开的形式一般化:

$$ \begin{aligned} \frac{a}{b} & =\frac{bq_{1} +r_{1}}{b} =q_{1} +\frac{r_{1}}{b} =q_{1} +\frac{1}{b/r_{1}}\\ \frac{b}{r_{1}} & =\frac{r_{1} q_{2} +r_{2}}{r_{1}} =q_{2} +\frac{r_{2}}{r_{1}} =q_{2} +\frac{1}{r_{1} /r_{2}}\\ \frac{r_{1}}{r_{2}} & =\frac{r_{2} q_{3} +r_{3}}{r_{2}} =q_{3} +\frac{r_{3}}{r_{2}} =q_{3} +\frac{1}{r_{2} /r_{3}}\\ \vdots & \\ \frac{r_{n-1}}{r_{n}} & =\frac{r_{n} q_{n+1} +r_{n+1}}{r_{n}} =q_{n+1} +\frac{r_{n+1}}{r_{n}} =q_{n+1} +\frac{1}{r_{n} /r_{n+1}} \end{aligned} $$

则当\(r_n\)整除\(r_{n+1}\)时,\(gcd(a,b)=gcd(r_n,r_{n+1})=r_{n+1}\),而其中的\(q_1,q_2,\cdots q_{n+1}\)即为欧几里德算法中出现的各个商。

2.3 最大公约数的线性表示

2.3.1 据题意,得:

$$ \begin{aligned} & ( 63,13) =( a,b)\\ \Rightarrow & ( 13,11) =( b,a-4b)\\ \Rightarrow & ( 11,2) =( a-4b,b-a+4b) =( a-4b,-a+5b)\\ \Rightarrow & ( 2,1) =( -a+5b,a-4b-5( -a+5b) =( -a+5b,6a-29b) \end{aligned} $$

则显然有\(gcd(63,13)=1\),且\((6,-29)\)是满足\(63m+13n\)的一个解。

2.3.2 可用欧几里德算法找到题目中线性不定方程的一组解:

$$ \begin{aligned} & ( 55,34) =( a,b)\\ \Rightarrow & ( 34,21) =( b,a-b)\\ \Rightarrow & ( 21,13) =( a-b,b-a+b) =( a-b,-a+2b)\\ \Rightarrow & ( 13,8) =( -a+2b,a-b-( -a+2b) =( -a+2b,2a-3b)\\ \Rightarrow & ( 8,5) =( 2a-3b,-a+2b-2a+3b) =( 2a-3b,-3a+5b)\\ \Rightarrow & ( 5,3) =( -3a+5b,2a-3b+3a-5b) =( -3a+5b,5a-8b)\\ \Rightarrow & ( 3,2) =( 5a-8b,-3a+5b-5a+8b) =( 5a-8b,-8a+13b)\\ \Rightarrow & ( 2,1) =( -8a+13b,5a-8b+8a-13b) =( -8a+13b,13a-21b) \end{aligned} $$

则显然有\((13,-21)\)是方程\(55m+34n=1\)的一组解。

2.4 质数与因式分解

2.4.1 使用题目中给出的思路,我们要证明如果\(a_1,b_1<p\),则\(p\nmid a_1b_1\)。我们假设\(p\mid a_1b_1\),且令\(b_2=p-q_1b_1\),则两边同时乘以\(a_1\)\(a_1b_2=pa_1-q_1a_1b_1\)。显然有\(p\mid pa_1\)\(p\mid q_1a_1b_1\),则可以得到\(p\mid a_1b_2\)。我们再令\(b_3=b_1-q_2b_2\),两边同时乘以\(a_1\)\(a_1b_3=a_1b_1-q_2a_2b_2\),同理有\(p\mid a_1b_3\)。如此我们得到\(b_n=b_{n-2}-q_{n-1}b_{n-1}\)使得\(p\mid a_1b_n\)。显然\(b_1,b_2,\cdots b_n\)会无穷递降下去,而这是不可能的,所以我们的假设只能是错误的,也即当\(a_1,b_1<p\Rightarrow p\nmid a_1b_1\)

2.4.2 已知\(p\mid ab\),假设\(p\nmid a\)\(p\nmid b\),则可设\(a=q_1p+r_1,b=q_2p+r_2\),显然\(r_1,r_2<p\),则有:

$$ ab=( q_{1} p+r_{1})( q_{2} p+r_{2}) =q_{1} q_{2} p^{2} +q_{1} r_{2} p+r_{1} q_{2} p+r_{1} r_{2} $$

显然前三项都可以整除\(p\),又因为我们假设\(p\mid ab\),则只能有\(p\mid r_1r_2\)。因为\(r_1,r_2<p\),这显然与我们在2.4.1证明的结论相矛盾,所以我们的假设是错误的,则\(p\mid a\)或者\(p\mid b\)

2.5 唯一因式分解的后果

2.5.1 举例来说\(gcd(-4,-9)=1\)即两者互质,且两者乘积为\(36\)是一个平方数,但是\(-4,-9\)都不是平方数,而是平方数的相反数。

2.5.2 举例来说\(gcd(-8,-27)=1\),两者的乘积为\(216\)是一个立方数,同时\(-8\)\(-27\)也是立方数。之所以会这样是因为负数的立方数还是一个负数。

2.5.3 据题意有\(2000=2^4\times5^3,2001=3\times23\times29\),显然两者的质因数分解中没有公共素数因子,则\(gcd(2000,2001)=1\)

2.5.4 根据最大公约数与最小公倍数的定义,不难推导出上述性质,这里从略。

2.5.5 根据2.5.4中给出的性质,有:

$$ \begin{aligned} gcd( a,b) lcm( a,b) & =p_{1}^{min( m_{1} ,n_{1}) +max( m_{1} ,n_{1})} p_{2}^{min( m_{2} ,n_{2}) +max( m_{2} ,n_{2})} \cdots p_{k}^{min( m_{k} ,n_{k}) +max( m_{k} ,n_{k})}\\ & =p_{1}^{m_{1} +n_{1}} p_{2}^{m_{2} +n_{2}} \cdots p_{k}^{m_{k} +n_{k}}\\ & =\left( p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}\right) \times \left( p_{1}^{n_{1}} p_{2}^{n_{2}} \cdots p_{k}^{n_{k}}\right)\\ & =ab \end{aligned} $$

2.5.6 既然\(q\)是一个质数,显然只有\(1,q\)两个因子,而\(2^{p-1}\)的因子分别为\(1,2,2^2\cdots2^{p-1}\),所以原式的因子两个部分因子的组合,即\(1,2,2^2\cdots,2^{p-1}\)\(q,2q,2^2q\cdots2^{p-2}q\)

2.5.7 根据上题结论,并根据等比数列求和公式,\(2^{p-1}q\)的所有真因子之和为:

$$ \begin{aligned} & \left( 1+2+2^{2} +\cdots 2^{p-2} +2^{p-1}\right) +\left( q+2q+2^{2} q+\cdots 2^{p-2} q\right)\\ = & \frac{1-2^{p-1}}{1-2} +2^{p-1} +q\frac{1-2^{p-1}}{1-2}\\ = & 2^{p-1} -1+2^{p-1} +2^{p-1} q-q\\ = & 2^{p} -1+\left( 2^{p} -1\right)\left( 2^{p-1} -1\right)\\ = & \left( 2^{p} -1\right)\left( 1+2^{p-1} -1\right)\\ = & \left( 2^{p} -1\right) 2^{p-1}\\ = & 2^{p-1} q \end{aligned} $$

2.6 线性丢番图方程

2.6.1\(a'=a/gcd(a,b),b'=b/gcd(a,b)\),显然\(a',b'\)都是整数且\(gcd(a',b')=1\),则有:

$$ am+bn=gcd(a,b)(a'm+b'n) $$

\((x_0,y_0)\)使得\(a'x_0+b'y_0=1\),则令\(m=x_0t,n=y_0t\),则有:

$$ a'm+b'n=a'x_0t+b'y_0t=(a'x_0+b'y_0)t=t $$

显然当\(t\)取遍整数时,\(a'm+b'n\)也可取遍所有整数,则\(am+bn\)包含\(gcd(a,b)\)的所有整数倍。

2.6.2 使用欧几里德算法有:

$$ \begin{aligned} & (34,19)=(a,b)\\ \Rightarrow & (19,15)=(b,a-b)\\ \Rightarrow & (15,4)=(a-b,b-a+b)=(a-b,-a+2b)\\ \Rightarrow & (4,3)=(-a+2b,a-b-3(-a+2b)=(-a+2b,4a-7b)\\ \Rightarrow & ( 3,1) =( 4a-7b,-a+2b-4a+7b) =( 4a-7b,-5a+9b) \end{aligned} $$

显然\((-5,9)\)是原方程的一个解。

2.6.3 显然只需要在方程\(34x+19y=1\)两边同时乘以\(7\)就得到题目中的方程,因此也只需要在上题方程的解上乘以\(7\)就可以得到方程\(34x+19y=7\)的一个解,即\((-35,63)\)

2.6.4 显然有\(gcd(34,17)=17 \nmid 1\),则该方程没有整数解。

2.7 向量欧几里得算法

2.7.1\(a,b\)的最大公约数为\(g\ne1\),则显然有\(m=a/g,n=b/g\)使得\(mb=na=ab/g\)

2.7.2 通过图2.1中的第二列,我们可以看到符号对的系数就对应着向量的坐标,所以当第一列的数字对变成\((1,-1)\)时,也就表明第二列的\(m_1a-n_1b=1\)以及\(m_2a-n_2b=-1\),从而第三列的向量分别构成了\(ax-by=1\)以及\(ax-by=-1\)的整数解。通过向量加法的过程,我们知道这样产生的解必然是正整数而且是逐渐增大的,所以第一个碰到的这样的解就是最小正整数解。

2.8 互质对的地图

2.8.1\(m_1n_2-m_2n_1=1>0\Rightarrow m_1n_2>m_2n_1\),两边同时除以\(n_1n_2\),则有\(m_1/n_1>m_2/n_2\)

2.8.2 从图中可以明显看出,每个二叉树的左分支的\(m_l/n_l\)总是大于右分支的\(m_r/n_r\),所以以此类推,整个图形中任意的出现在左边的\(m_1/n_1\)要大于右边的\(m_2/n_2\)

2.8.3 既然每个左边的\(m_1/n_1\)都要大于右边的\(m_2/n_2\),所以图形中每一对\((m,n)\)显然都应该不同的,也就是说不可能重复出现。