分而治之

定义和例子

定义1：自然数被定义为：\(\{ 1, 2, 3, 4... \}\)

定义2：整数被定义为：\(\{..., -3, -2, -1, 0, 1, 2, 3, ...\}\)

定义3：假定\(a\)和\(d\)是两个整数，我们定义\(d\)整除\(a\)，记做\(d\mid a\)，当且仅当存在一个整数\(k\)，使得\(a=kd\)。

定义4：假定\(a, b\)以及\(n\)是整数，且\(n\gt 0\)。我们说，\(a和b\)同模于\(n\)当且仅当\(n\mid (a-b)\)，记为\(a\equiv b \pmod{n}\)。读作“a与b同模于n”。

定理：令\(n\)为一整数，如果\(6\mid n\)，则\(3\mid n\)。

证明：根据定义3，如果\(6|n\)，则存在一个整数\(k\)，使得\(n=6*k\)，则\(n=6*k=3*(2k)\)，若令\(k'=2k\)，则\(n=3*k'\)，满足定义3的定义，所以\(3\mid n\)。

定理：令\(k\)为一整数，如果\(k\equiv 7\pmod{2}\)，那么\(k\equiv3\pmod{2}\)。

证明：因为\(k\equiv 7\pmod{2}\)，所以根据定义4，\(2|(k-7)\)，再根据定义3，存在一个整数\(n\)，使得\(k-7=2*n\)，等式两边各加4，得到\(k-3=2*(n+2)\)，所以\(2|(k-3)\)，也就是\(k\equiv3\pmod{2}\)。

整除性和同模

定理1.1：令\(a, b, c\)为整数，如果\(a\mid b\)且\(a\mid c\)，则\(a\mid (b+c)\)

证明：根据定义3，\(a\mid b\)表明\(b=a*k_1\)，\(a\mid c\)表明\(c=a*k_2\)，所以\(b+c=a*(k_1+k_2)\)，所以\(a\mid (b+c)\)。证毕。

定理1.2：令\(a, b, c\)为整数，如果\(a\mid b\)且\(a\mid c\)，则\(a\mid (b-c)\)

定理1.3：令\(a, b, c\)为整数，如果\(a|b\)且\(a\mid c\)，则\(a\mid (b*c)\)

以上两个定理的证明不难。请自行完成。

定理的加强：如果前提变弱，但可以得到相同的结论；或者前提不变，但可以得到更强的结果，则称为定理得到加强。

以定理1.3为例，两种加强该定理的方法是：

定理1.3-1：令\(a, b, c\)为整数，如果\(a\mid b\)且\(a\mid c\)，则\(a^2\mid (b*c)\)

定理1.3-2：令\(a, b, c\)为整数，如果\(a\mid b\)，则\(a\mid (b*c)\)

接下来看看同模的一些定理。

定理1.9：令\(a\)和\(n\)为整数，且\(n\gt0\)，那么\(a\equiv a\pmod{n}\)

定理1.10：令\(a, b, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}\)，则\(b\equiv a\pmod{n}\)。

定理1.11：令\(a, b, c, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}\)，且\(b\equiv c\pmod{n}\)，则\(a\equiv c\pmod{n}\)。

证明：由题设，\(a-b=k_1*n\)，\(b-c=k_2*n\)，两式相加得到：\(a-c=(k_1+k_2)*n\)，根据定义3和4，\(a\equiv c\pmod{n}\)。QED

以下的定理描述了同模的加、减和乘运算，除法运算需要另外考虑。

定理1.12：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(a+c\equiv b+d\pmod{n}\)。

定理1.13：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(a-c\equiv b-d\pmod{n}\)。

定理1.14：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(ac\equiv bd\pmod{n}\)。

这些证明都不是很难。请自行完成。

同模运算也可以用在指数运算上。证明时需要用到数学归纳法。

定理1.18：令\(a, b, k, n\)为整数，且\(n\gt0, k\gt0\)。若\(a\equiv b\pmod{n}\)，则\(a^k\equiv b^k\pmod{n}\)

证明：

\(k=1\)时，定理显然成立。

假定k=p时，定理仍然成立。

\(k=p+1\)时，\(a^{p+1}b^{p+1}=(a^p*b^p)*(a*b)\)，结合\(k=1\)以及\(k=p\)的情形，得到\(a^p \equiv b^p\pmod{n}\)以及\(a \equiv b\pmod{n}\)，根据定理1.14，得到\(a^{p+1} \equiv b^{p+1}\pmod{n}\)。QED。

有兴趣的读者，可以针对上述定理，用一些数字加以测试和验证。

定理1.21：令自然数\(n\)可以以10进制表述为：\(n=a_ka_{k-1}...a_1a_0\)，如果\(m=\sum_{i=0}^ka_i=a_k+a_{k-1}+a_1+a_0\)，则\(n\equiv m\pmod{3}\)。

证明：\(n\)可以进一步写作\(n=3*(3*a_k)*10^k+a_k*10^k+3*(3*a_{k-1})*10^k+a_{k-1}*10^k+...+3*(3*a_1)*10^1+a_1*10^1+a_0=3*\sum_{i=1}^k 3*a_i*10^i+\sum_{j=0}^k a_j=3*\sum_{i=1}^k 3*a_i*10^i+m\)。因此，3（甚至9）可以整除\(n-m\)，所以\(3|n-m\)。根据定义4，\(n\equiv m\pmod{3}\)。QED。

有了以上这些定理，我们可以开始证明一些有关数字的有趣内容。比如，我们从小就学到的，一个自然数能被3整除当且仅当这个自然数的各位数字之和能被3整除。

用严格的数学描述这个定理就是：

定理1.22：如果一个自然数能被3整除，那么该自然数以10进制表达的各数位之和可以被3整除。

定理1.23：如果一个自然数以10进制表达的各数位之和可以被3整除，那么这个自然数可以被3整除。

这个证明不难，请读者自行完成。

注意：上述的定理中出现了当且仅当这样的描述，这样的定理需要两个独立的证明，分别证明充分性（sufficiency）和必要性（necessity），只从一个“方向”证明是不完备的。

接下来要讲述除法时的同模性。该定理被称为除法算法（Division Algorithm）。

除法算法

首先介绍一个公理，称为 自然数的良序公理（原理）(Well-ordering principle of natural numbers） 。

令\(S\)为自然数的一个任意的非空集合，那么\(S\)一定有一个最小的元素。

除法算法：令\(n\)和\(m\)为任意自然数，则存在一个整数\(q\)和另一个整数\(r\)，使得\(m=nq+r\)，且\(0\le r \le n-1\)。（存在性）同时，我们称\(q\)为商（quotiant），\(r\)为余数（remainder）。同时，如果任意\(q, q', r, r'\)满足：\(m=nq+r=nq'+r'\)，且\(0\le r, r' \le n-1\)，那么\(r=r', q=q'\)。（唯一性）

证明：（存在性）

如果\(m\lt n\)，那么\(q=0, r=m\lt n (\le n-1)\)。

如果\(m=n\)，那么\(q=1, r=0\)。

如果\(m\gt n\)，那么存在一系列\(q_i\)，使得\(n*q_i \ge m\)。根据良序公理，存在一个最小的\(q_j\)，使得\(n*q_j-m\lt n (\le n-1)\)——否则一定存在一个更小的\(q_{j'}\)，使得\(n*q_{j'}-m\le n-1\)。这个\(j\)就是我们要找的\(q\)，而\(n*q-m\)就是我们要找的\(r\)，且满足\(0\le r \le n\)。存在性证毕。

证明：（唯一性）

假定存在\(m=n*q+r=n*q'+r'\)。这表明\(n(q-q')=r'-r\)，也就是\(n|r'-r\)。因此要么\(|r'-r|\ge n\)，要么\(r'-r=0\)。由于\(0\le r, r'\lt n\)，所以\(|r'-r|\lt n\)，因此只能是\(r'-r=0\)，也就是\(r=r'\)，进而\(q=q'\)。唯一性证毕。

证明了除法算法后，可以引入如下定理。

定理1.28：令\(a, b, n\)为整数，且\(n\gt 0\)。那么\(a\equiv b\pmod{n}\)当且仅当\(n\)除\(a, b\)时有相同的余数。等价描述是，\(a\equiv b\pmod{n}\)当且仅当\(a=nq_1+r_1 (0\le r_1 \le n-1), b=nq_2+r_2 (0\le r_2 \le n-1)\)，且\(r_1=r_2\)。

这个定理的充分必要性证明不难。请自行完成。

最大公约数（GCD）及线性丢番都方程

定义：整数\(a, b\)的公约数是指这样一个整数\(d\)，使得\(d\mid a\)且\(d\mid b\)。

定义：两个整数\(a, b\)（两者不同时为0）的最大公约数是最大的一个整数\(d\)，使得\(d\mid a\)且\(d\mid b\)。\(a, b\)的最大公约数通常记为\(gcd(a, b)\)或者简单记为\((a, b)\)。

定义：如果\(gcd(a, b)=1\)，那么\(a, b\)被称为互质（relatively prime）。

定理1.32：令\(a, n, b, r, k\)为整数。如果\(a=nb+r, k\mid a, k\mid b\)，则\(k\mid r\)。

证明：因为\(k\mid a, k\mid b\)，由定义3，\(a=ka', b=kb', r=a-nb=ka'-knb'=k(a'-nb')\)，因此\(k\mid r\)。

定理1.33：令\(a, b, n_1, r_1\)为整数，且\(a, b\)不同时为0。如果\(a=n_1b+r_1\)，那么\((a,b)=(b,r1)\)。

证明：令\(k=(a,b)\)，那么\(a=k*a', b=k*b', r_1=a-n_1*b=k(a'-n_1b')\)，显然\(k|b, k|r_1\)，也就是说\(k\)是\(b\)和\(r_1\)的公约数。假定存在\(k'\gt k\)，而且也是\(b\)和\(r_1\)的一个更大的公约数，那么\(a\)也将有\(k'\)这个因子，因此\((a,b)=k'\)，与题设矛盾。所以\(k\)就是\(b, r_1\)的最大公约数。QED。

定理1.33非常重要。从中我们可以得到求GCD最有效的方法，也就是由欧几里得老师发明的辗转相除法。

练习1.35：求\((51, 15)\)。

解：

\(51=3*15+6 (a=51, b=15, r=6)\)

于是\((51,15) = (15, 6) \implies 15=2*6+3\:(a=15, b=6, r=3) \implies (15,6)=(6,3) \implies 6=2*3+0\)。

因此，\((6,3)=3\)，亦即\((51, 15)=3\)。

练习1.36：利用辗转相除法求下列各对数的GCD

1. (96, 112)
2. (175, 24)
3. (0, 256)
4. (-288, -166)
5. (1, -2436)

练习1.37：找出整数\(x, y\)，使得\(175x+24y=1\)。

在解这道题之前，我们先做几个简单的类似练习，看看能不能找出规律。

\(3x+5y=1\)

解：通过简单的凑数，我们可以发现\(x=2, y=-1\)是一组解，\(x=7, y=-4\)是第二组解，\(x=12, y=-7\)是第三组解。这样的解有无穷多组。但可以写成通式：\(x=5n+2, y=-3n-1\)。

在这个通式中，\(5n, -3n\)是很容易理解的，因为随着\(|n|\)越来越大，\(3x+5y\)必须要消除掉这个无穷大项才能得到一个有限值。由于\((3,5)=1\)，所以，\(x\)必然形如\(5n+a\)，而\(y\)必然形如\(-3n+b\)。

下面我们利用辗转相除法求\((5,3)\)的方式来得到一个具体解。

根据定理1.33，我们可以得到：

1. \(5=3(1)+2\)
2. \(3=2(1)+1\)

我们看到最后一个等式的右边出现了1。我们将最后一个等式改写：

\(1=3(1)-2(1)\)

根据第一个式子：\(2=5(1)-3(1)\)，代入上式，得到：

\(1=3(1)-(5(1)-3(1))=3(2)+5(-1)\)

结合我们要求的等式：\(3x+5y=1\)，可以得到\(x=2, y=-1\)。

有了一个特征解后，我们可以令\(n=0\)，得到\(a=2, b=-1\)。

因此，\(3x+5y=1\)的通解公式就是：

\(x=5n+2, y=-3n-1, n\in Z\)

\(47x+30y=1\)

解：

\(47=30(1)+17\)

\(30=17(1)+13\)

\(17=13(1)+4\)

\(13=4(3)+1\)

因此：

\(*=1=13(1)-4(3)\)

\(*=13(1)-(17-13)(3)=13(4)+17(-3)\)

\(*=[30(1)+17(-1)](4)-17(3)\)

\(*=30(4)+17(-7)\)

\(*=30(4)+[47(1)+30(-1)](-7)\)

\(*=47(-7)+30(11)\)

因此，对于\(47x+30y=1\)，我们有一个特征解\(x=-7, y=11\)。

其通解一定形如：\(x=30n+a, y=-47n+b\)。

令\(n=0\)，我们得到\(a=-7, b=11\)。于是该方程的通解为：

\(x=30n-7, y=-47n+11, n\in Z\)

我们用个表来验算几个解：

n	x=30*n-7	y=-47n+11	47x+30y
-4	-127	199	1
-3	-97	152	1
-2	-67	105	1
-1	-37	58	1
0	-7	11	1
1	23	-36	1
2	53	-83	1
3	83	-130	1
4	113	-177	1

现在我们可以来求解\(175x+24y=1\)了。我们的步骤如下：

1. \(175=24(7)+7\)
2. \(24=7(3)+3\)
3. \(7=3(2)+1\)

进一步得到：

\(*=1=7+3(-2)\)

\(*=7(1)+[24-7(3)](-2)=24(-2)+7(7)\)

\(*=24(-2)+[175-24(7)](7)=175(7)+24(-51)\)

所以\(175*7+24*(-51)=1\)。我们得到了一组解。其通解形式一定形如：\(x=24n+a, y=-175n+b\)。令\(n=0\)，得到：\(a=7, b=-51\)。因此其通解为：

\(x=24n+7, y=-175n-51, n\in Z\)

上述的几个例子，是一个定理的特例。我们将这个定理一般化，可以得到如下的一个重要定理。

定理：令\(a, b\)为整数。则\((a, b)=1\)当且仅当存在整数\(x, y\)使得\(ax+by=1\)。

同样，因为这个定理中出现了当且仅当，所以可以将其拆成两个定理。

定理1.38：令\(a, b\)为整数。如果\((a, b)=1\)，则存在整数\(x, y\)使得\(ax+by=1\)。

定理1.39：令\(a, b\)为整数。如果存在整数\(x, y\)使得\(ax+by=1\),则\((a, b)=1\)。

我们先证明定理1.38。首先我们需要假定欧几里得的辗转相除法是“有限步数”的，也就是它会在\(n\)步之后结束，并在我们的这个特例中，得到最大公约数1。证明辗转相除法可以在有限步骤内完成，超出了本书的范围。

首先，如果一步就能得到\((a, b)=1\)，也就是\(a=b*y+1\)。于是\(1=a*1+b*(-y)\)，我们找到了符合条件的\(x, y\)。

其次，假定需要两步才能得到\((a, b)=1\)。

1. \(a=bq_1+r_1\)
2. \(b=r_1q_2+1\)

于是：\(1=a(-q_2)+b(1+q_1q_2)\)，于是我们得到\(x=-q_2, y=1+q_1q_2\)。这个特征解和余数无关，而只和辗转相除时的商有关。

例如在上面的练习中，我们用：

1. \(5=3(1)+2\)
2. \(3=2(1)+1\)

两步得到了\(1=5(-1)+3(2)\)。其中的\(q_1=q_2=1\)，因此相应的\(x=-q_2=-1, y=(1+q_1q_2)=2\)，与我们得到的公式相符合。

第三，假定需要三步才能得到\((a, b)=1\)。

1. \(a=bq_1+r_1\)
2. \(b=r1q_2+r_2\)
3. \(r1=r2q_3+1\)

于是\(1=a(1+q_2q_3)+b(-(q_1+q_3+q_1q_2q_3))\)，我们也找到了\(x, y\)。结合上面的练习，我们用：

1. \(175=24(7)+7\)
2. \(24=7(3)+3\)
3. \(7=3(2)+1\)

三步得到了\(1=175*(7)+24*(-51)\)，其中\(q_1=7, q_2=3, q_3=2\)，代入上述公式我们得到：\(x=1+q_2q_3=7, y=-(q_1+q_3+q_1q_2q_3)=-51\)。和我们之前的手动计算一致。

更多步数我们不再演示。在上述过程中，各个步骤的余数\(r_i\)都是可以用\(f(a, b, q_i, r_{i-1})\)替代掉的。这个过程都是线性过程，所以，我们可以得到一个特征解。QED。¹

接下来我们证明定理1.39：令\(a, b\)为整数。如果存在整数\(x, y\)使得\(ax+by=1\),则\((a, b)=1\)。

证明：

我觉得可以用反证法。如果存在\(ax+by=1\)，但是\((a, b)\gt1\)，那么经过欧几里得的辗转相除法后，最后一步无法得到1。也因此，无法通过定理1.38中演示的过程反向得到\(ax+by=1\)。QED。

综上，通过定理1.38和定理1.39的证明，我们得到了一个重要的定理：

定理：令\(a, b\)为整数。则\((a, b)=1\)当且仅当存在整数\(x, y\)使得\(ax+by=1\)。

重要补充：另外，上面用辗转相除法得到公约数（1）然后再反向进行替换的做法是很繁琐的、而且容易出错。

在网络上我找到了一种更简便也更直观的做法。我们用\(47x+30y=1\)来进行演示如下。

步骤	操作	等式形式	简写形式
1	-	47=1(47)+0(30)	47 1 0
2	-	30=0(47)+1(30)	30 0 1
3	1-2	17=1(47)-1(30)	17 1 -1
4	2-3	13=-1(47)+2(30)	13 -1 2
5	3-4	4= 2(47)-3(30)	4 2 -3
6	4-5(*3)	1=-7(47)+11(30)	1 -7 11
7	5-6*4	0=30(47)-47(30)	0 30 47

其中的第6行，给出了一个特征解：\(1=-7*(47)+11(30)\)，而最后的第7行，称为齐次解（因为最后答案为0）。\(ax+by=0\)永远有解，但在\((a, b)=1\)的情况下，\(a*b-b*a=0\)是其绝对值最小的一组特征解。但我们很快会看到，如果最后的得数不是\(1\)，也就是说\((a, b)\neq 1\)时，这个答案不是那么显然——但还是很容易求解的。

另外，辗转相除法可以直接生成连分数。

比如上面的例子中：

步骤	除法算法	分数形式
1	47=1*30+17	\(\frac{47}{30}=1+\frac{17}{30}\)
2	30=1*17+13	\(\frac{30}{17}=1+\frac{13}{17}\)
3	17=1*13+4	\(\frac{17}{13}=1+\frac{4}{13}\)
4	13=3*4+1	\(\frac{13}{4}=3+\frac{1}{4}\)

所以：

\(\frac{47}{30}=1+\frac{17}{30}=1+\frac{1}{1+\frac{13}{17}}=1+\frac{1}{1+\frac{1}{1+\frac{4}{13}}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{3+\frac{1}{4}}}}\)

是不是很美丽？

接下来，我们将刚才证明的定理加以扩充，得到一个更普遍的定理：

定理1.40（Bezout引理）：对任意的整数\(a, b\)，且\(a, b\)不同时为0，则必然存在一对整数\(x, y\)，使得\(ax+by=(a, b)\)

证明：

显然，如果\((a, b)=1\)，我们回到了定理1.38和1.39的形式。

如果\((a, b)=k\neq 1\)，那么\(ax+by=k\)可以改写成：\(a'kx+b'ky=k\)，于是等式转化为求\(a'x+b'y=1\)。根据定理1.38+1.39，一定可以得到这组解。得到这组解后，等式两边同时乘以\(k\)，就可以得到\(ax+by=(a, b)\)。反之亦然。QED。

另一个证明：

给定给定条件的\(a, b\)，令\(S={ax+by\mid x, y\in Z, ax+by\gt0}\)，集合\(S\)显然不会为空，因为当\(x=\pm1, y=0\)时，必然可以得到\(\pm a\)，其中有一个肯定是\(S\)的元素。根据良序原理，一定存在一个最小的元素\(min=as+bt\)，使得：\(a=min*q+r, 0\le r\lt min\)

于是：\(r=a-min*q=a-q(as+bt)=a(1-qs)+b(-qt)\)。

因为\(r\)可以写成\(ax+by\)的形式，所以\(r\in S \cup \{0\}\)。但是，\(0\le r\lt min\)，而\(min\)已经是\(S\)中最小的元素，所以\(r\)只能为0，所以\(min\mid a\)，同理可证\(min\mid b\)，所以\(min\)是\(a, b\)的公约数。

假定\(m'\)也是\(a, b\)的公约数，所以\(a=m'u, b=m'v\)，因此\(d=as+bt=m'us+m'vt=m'(us+vt)\)，也就是说\(c\le d\)。因此，\(d\)已经是最大的公约数。QED。

定理1.41：令\(a, b, c\)为整数，如果\(a|bc, (a, b)=1\)，则\(a|c\)。

证明：根据定理，\((a, b)=1\)表明存在\(x, y\)使得\(ax+by=1\)。等式两边同乘以\(c\)，得到：

\(acx+bcy=c\)。注意到，\(a\mid acx, a\mid bcy\)，所以等式左边的式子可以被\(a\)整除，所以\(a\mid c\)。QED。

定理1.42：令\(a, b, n\)为整数，如果\(a\mid n, b\mid n, (a, b)=1\)，则\(ab\mid n\)。

证明：由\((a, b)=1\)，得\(ax+by=1 \implies anx+bny=n\)。又由\(a\mid n, b\mid n \implies n=k_1a, n=k_2b\)，因此\(anx+bny=abk_2x+abk_1y=n \implies ab(k_1y+k_2x)=n\)，显然\(ab\mid n\)。QED。

定理1.43：令\(a, b, n\)为整数，且\((a, n)=1, (b, n)=1\)，则\((ab, n)=1\)。

证明：略。请自行完成。

我们继续向着解决丢番都方程进发。

定理1.45：令\(a, b, c, n\)为整数，\(n\gt0\)，如果\(ac\equiv bc\pmod{n}, (c, n)=1\)，则\(a\equiv b\pmod{n}\)。

证明：

由题设得，\(ac-bc=kn \implies (a-b)c=kn\)。这表明\(c\mid kn\)。根据定理1.41, 如果\(c\mid kn\)，且\((c, n)=1\)，那么\(c\mid k\)。假定\(k=k'c\)，于是\(c(a-b)=kn=k'cn \implies a-b=k'n\)，因此\(a\equiv b\:\pmod{n}\)。QED。

定理1.48：令\(a, b, c\)为整数，且\(a, b\)不同时为0，则存在整数\(x, y\)满足等式\(ax+by=c\)当且仅当\((a, b)\mid c\)。

证明：

令\((a, b)=k\)，于是\(k\mid a, k\mid b\)，因此\(a, b\)可以写成：\(a=ka', b=kb'\)。\(c=ax+by=ka'x+kb'y=k(a'x+b'y)\)。因此\(k\mid c\)。

反过来，假定\((a,b)=d, d\mid c\)，则\(c=kd\)，根据定理1.40，存在\(x', y'\)使得\(ax'+by'=d\)，于是\(ax'k+by'k=kd \implies ax+by=c\)。QED。

有了这些准备工作，我们已经在解决丢番都问题的路上走得很远了。我们看两个定理：

定理1.51：令\(a, b, c, x_0, y_0\)为整数，且\(a, b\)不同时为0，且\(ax_0+by_0=c\)，那么整数：\(x=x_0+\frac{b}{(a,b)}, y=y_0-\frac{a}{(a,b)}\)也满足丢番都线性方程\(ax+by=c\)。

这个定理的证明很简单。但是，这个定理不完整：我们知道这个形式的\(x, y\)是方程的解，但是不是还有别的形式的解呢？

定理1.53：令\(a, b, c,\)为整数，且\(a, b\)不同时为0。如果\(x=x_0, y=y_0\)是方程\(ax+by=0\)的一组整数解，那么对于所有的整数\(k\)，\(x=x_0+\frac{kb}{(a,b)}, y=y_0-\frac{ka}{(a,b)}\)也满足丢番都线性方程\(ax+by=c\)，且所有该方程的解必然具有这种形式。

证明：

我们先证明，如此形式的\(x, y\)是方程的解。

\(ax+by=a(x_0+\frac{kb}{(a, b)})+b(y_0-\frac{ka}{(a, b)})=ax_0+by_0+\frac{abk}{(a, b)}-\frac{abk}{(a, b)}=c\)。QED。

我们假定还有别的形式，那么这样的\(x,y\)一定可以写成：\(x=x_0+\frac{kb}{(a,b)}+x', y=y_0-\frac{ka}{(a,b)}+y'\)。代入方程后，经过简化可以得到：\(ax'-by'\equiv 0\)。对于特定的\(a, b\)，\(x', y'\)要么都是0，于是这个解的形式退化为通解形式；要么形如\(ma, mb \implies \frac{m(a, b)a}{(a, b)}, \frac{m(a, b)b}{(a, b)}\)，可以合并到通式。QED。

另一种证明是：

已知\(ax_0+by_0=c, ax+by=c\)，两式相减得到：\(a(x_0-x)+b(y_0-y)=0 \implies \frac{x_0-x}{b}=\frac{y-y_0}{a}\)。这两个式子，一个是与\(x\)有关，一个与\(y\)有关，要想这个等式对所有的\(x, y\)成立，那么必然等于一个常数\(-k\)。于是：\(x_0-x=-kb, y-y_0=-ka\)，得到：\(x=x_0+kb, y=y_0-ka\)。

练习1.54：找到方程\(24x+9y=33\)的所有解。

解：\(x=y=1\)显然是方程的一个特解。\((24, 9)=3\)。因此该方程通解具有如下形式：\(x=1+\frac{k*9}{3}=1+3k, y=1-\frac{k*24}{3}=1-8k\)。简单列出几个解如下：

\(k\)	\(x=1+3k\)	\(y=1-8k\)	\(24x+9y\)
-5	-14	41	33
1	4	-7	33
3	10	-23	33

我们对于线性丢番都方程的分析到此完成。定理1.53就是我们的最终分析结果。

在证明了定理1.53后，我们可以证明一个非常直观的定理。

定理1.54：若\(a, b\)为整数且不同时为0，而\(k\)是一个自然数，那么\(gcd(ka, kb)=k*gcd(a, b)\)。

证明：

我们先不用定理1.53来证明。

我们知道，任何一个整数都可以表示为一系列质数因子各次方的乘积，也就是说：

\(a=p_1^{r_1}p_2^{r_2}...p_n^{r_n}...\)

\(b=p_1^{s_1}p_2^{s_2}...p_n^{s_n}...\)

根据最大公约数的定义，\((a, b)=p_1^{min(r_1, s_1)}p_2^{min(r_2, s_2)}...p_n^{min(r_n, s_n)}...\)。

对于\((ka, kb)\)，其中的\(k\)也可以同样写成\(k=p_1^{t_1}p_2^{t_2}...p_n^{t_n}...\)，于是：

\(ka=p_1^{r_1+t_1}p_2^{r_2+t_2}...p_n^{r_n+t_n}...\)

\(kb=p_1^{s_1+t_1}p_2^{s_2+t_2}...p_n^{s_n+t_n}...\)

因此，\((ka, kb)=p_1^{min(r_1+t_1, s_1+t_1)}p_2^{min(r_2+t_2, s_2+t_2)}...p_n^{min(r_n+t_n, s_n+t_n)}...\)。

注意到：\(min(a+x, b+x)=x+min(a, b)\)，所以\((ka, kb)=p_1^{t_1}p_2^{t_2}...p_n^{t_n}...*p_1^{min(r_1, s_1)}p_2^{min(r_2, s_2)}...p_n^{min(r_n, s_n)}...=k*(a, b)\)。QED。

用到定理1.53的证明如下：

令\(g=(a, b)\)，那么\(g\)就是\(ax+by\)能得到的最小自然数值。所以\((ka, kb)\)就是\(akx+bky\)能得到的最小自然数值，也就是\(k*(ax+by)的最小值\)，也就是\(k*g\)。QED。

我们已经知道GCD的概念：它是所谓的公约数，也就是这里牵涉到了整除。那么对于倍数（乘法），我们有怎样的值呢？那就是最小公倍数（LCM, Least Common Multiplier)。

定理1.57：如果\(a, b\)为自然数，那么\(gcd(a, b)*lcm(a, b)=ab\)。

推论1.58：如果\(a, b\)为自然数，那么\(lcm(a, b)=ab\)当且仅当\(a, b\)互质。

证明：

我们先证明一个引理：如果\(m\gt0\)，那么\(lcm(ma, mb)=m*lcm(a, b)\)。

因为\(lcm(ma, mb)\)是\(ma\)的倍数，也就肯定是\(m\)的倍数，也就是说\(m\mid lcm(ma, mb)\)。

令\(mh_1=lcm(ma, mb), h_2=lcm(a, b)\)。

\(ma|mh_1 \implies a|h_1, mb|mh_1 \implies b|h_1\)。因此\(h_1\)是\(a, b\)共同的倍数。但我们已经知道\(h_2\)是最小公倍数，所以\(h_1\ge h_2\)。

同时，\(a\mid h_2 \implies am\mid mh_2, b\mid h_2 \implies bm\mid mh_2\)，所以\(mh_2\)是\(ma, mb\)的公倍数，而\(mh_1\)才是\(ma, mb\)的最小公倍数，所以\(mh_2 \ge mh_1 \implies h_2\ge h_1\)。

综上，\(h_1=h_2\)。引理证明完毕。

令\(g=(a, b) \implies a=gc, b=gd\)。因此\((c, d)=(a/g, d/g)=1\)。

\(c\mid lcm(c,d) \implies lcm(c, d)=kc\)。由于\(d\mid kc, (c,d)=1, d\mid k\)，因此\(cd\le kc\)。但\(cd\)是一个倍数，而\(kc\)是最小公倍数，所以\(kc\le cd\)。综合一下，只能是\(kc=cd\)，也就是\(lcm(c,d)=cd\)。

结合引理我们得到：

\(lcm(a, b)*gcd(a,b)=lcm(gc, gd)*g=g*lcm(c, d)*d=gcdg=(gc)(gd)=ab\)。QED。

综上，本章围绕着所谓丢番都方程进行了完整的分析。对于形如\(ax+by=c\)这样的方程，我们知道：

1. 怎样的情况下这个方程有整数解：定理1.48
2. 如何找到一个特征解：辗转相除法以及一种实际上使用的直观方法
3. 如何找到通解公式：定理1.53

丢番都方程以希腊数学家亚历山大的丢番都（或译作丢番图）命名。关于他的介绍请见《上帝创造整数：丢番都》。

线性丢番都方程通解的研究最早由5世纪印度数学家进行，直到17世纪西欧才开始有进展。欧拉、拉格朗日对此都做出了重要贡献。

实际应用

在实际应用中，我们结合上述定理可以对形如\(ax+by=c\)的方程求\(x, y\)的正整数解（\(a, b\gt 0\)）。

比如，老王有500元钱去买鸡。公鸡一只20元，母鸡一只16元。他准备把所有的钱都花掉，问他有几种可行的买法？

这个问题可以简化为：\(20x+16y=500\)，一个标准的丢番都方程。

解：

本题中，\(a=20, b=16, (a,b)=4, 4\mid 500\)，根据定理1.48，这个方程有整数解。

很容易看出\(x=125, y=-125\)是一个特解。

根据定理1.53，通解形式应该是：

\(x=x_0+\frac{k*b}{(a,b)}=125+4k, y=-125-5k\)

因为我们是在求正整数解，所以\(0\le x\le 25, 0\le y\le 31\)，而\(-31.25\le k \le -25\)。

列表求解（可以用Excel进行自动计算）如下：

k	x=125+4k	y=-125-5k	20x+16y
-32	-3	35	500
-31	1	30	500
-30	5	25	500
-29	9	20	500
-28	13	15	500
-27	17	10	500
-26	21	5	500
-25	25	0	500
-24	29	-5	500

开放问题：本章中我们讨论了整除性、最大公约数、丢番都方程的解。这些概念是怎样联系在一起的呢？

译者小结：本章应该属于数论的入门。我可以证明一些定理。最大的收获是学会了解丢番都方程。