分而治之

本页面已浏览121次

定义和例子

定义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

接下来我们证明定理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

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

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


  1. 我觉得我这个证明不是很严格。不过也就是我能达到的水平了。TA 

Next Post