标题:
初等数论入门(2)—最大公因数理论与一次不定方程
[打印本页]
作者:
51hei小名
时间:
2016-6-20 22:06
标题:
初等数论入门(2)—最大公因数理论与一次不定方程
本节我们先来介绍
最大公因数理论
剩下的部分，然后再用
最大公因数理论的观点
来看看
一次不定方程
。
本节的主题是：
最大公因数理论
、
一次不定方程
。
（注：这篇文章可以跟我很久以前写的一篇文章衔接（
注意：那篇文章有些不严谨
）。有兴趣的读者可以去看那篇文章：
一次不定方程的解法
。本文将修改并引用其中一些内容。）
我们先来完整地
阐述
最大公因数理论（其实最小公倍数也属于最大公因数理论）：
定义5
如果存在一个d使d|q1,d|q2,…d|qk，那么我们称d是q1,q2,…qk的
公因数
。如果这个d是所有公因数中最大的，那么我们称这个d叫做q1,q2,…,qk的
最大公因数
，记作(q1,q2,…,qk)
定义6
如果存在一个L
使q1|L,q2|L,…,qk|L，那么我们称d是q1,q2,…qk的
公倍数
。如果这个d是所有公倍数中最小的且是正的，那么我们称这个L叫做q1,q2,…,qk的
最小公倍数
，记作[q1,q2,…,qk]
定理2
最大公因数和最小公倍数具有如下性质：
1).q1,q2,q3,…,qk都整除c等价于[q1,q2,…,qk]|c。这是最小公倍数的本质特征：
公倍数一定是最小公倍数的倍数
。
2).D=(q1,q2,…)等价于D|q1,D|q2,……且对任给的满足d|q1,d|q2……的d，都有d|D。这是最大公因数的本质特征：
公因数一定是最大公因数的因数
。且如果一个数是公因数，而且它被其他的公因数整除，那么它是最大公因数。
在上一节我们已经证明了两个数的情景。
3).m(q1,q2,…)=(mq1,mq2,…)。就是说，
一些数的最大公因数的倍数等于这些数的倍数的最大公因数
。
在
上一节我们已经证明了两个数的情景。
4).(q1,q2,q3,…,qk)=((q1,q2),q3,…,qk)，且(q1,q2,…,qk)=((q1,q2,…,qr),(q(r+1),…,qk))
5).(a,b)=1，a|bc那么就有a|c。
上一节里这个结论已经证明了。
6).(a,b)=1那么就有
(a,bc)=(a,c)
7).[a,b](a,b)=|ab|，这里|ab|表示ab的绝对值。如果我们限制a和b都是正整数，那么可以表述为：[a,b](a,b)=ab，即
两个正整数的最大公因数与他们的最小公倍数的乘积等于这两个数的乘积
。
这里
我们只考虑a,b是正整数的情形。这个结论上一节已证明。
8).给定a,b，若记所有形如ax+by的数的集合为T，那么(a,b)=T中的最小正整数。
上一节这个结论已经证明了。
9).8)可推广为：给定q1,q2,q3,…,qk,那么(q1,q2,…,qk)=T中的最小正整数。这里T是所有形如q1x1+q2x2+…+qkxk的数的集合。
上一节我们证明了两个数的情景。
10).一定存在x，y使(a,b)=ax+by
我们来证明
证(1)
：
我们记
[q1,q2,…,qk
]=L，显然如果L|c，那么qi|L可得qi|c。(i=1,2,…,k)
现在只需证明如果q1|c,q2|c,…,qk|c，那么有L|c。设c=Lq+r (0≤r＜L)
那么r=c-Lq，由于qi|L,qi|c得qi|r。(i=1,2,…,k)，那么得到r也是q1,q2,…,qk的公倍数。如果r>0就与L是最小公倍数矛盾。，因此r=0。所以c=Lq，即L|c。
证(2)
：显然，如果能证明(4)，那么证明多个数的情形可以化归为两个数的情形，而这已经被证明了（第二节引理8）。如果能证明(9)，那么这个结论可以被直接证明。
第二节中，我们使用了较为高级的方法来证明引理8，现在我们给出几种引理8的其他证法。
引理8
如果s|a,s|b那么s|(a,b)。即两个数的公因数一定是他们的最大公因数的因数。
第2节中给出的证明：由引理7知可设(a,b)=ax+by，那么s|a,s|b可得s|ax+by=(a,b)。
新的证法：设d=(a,b)，显然s≤d。d|a,s|a可得[s,d]|a，d|b,s|b可得[s,d]|b，[s,d]也为a,b的公因数，故[s,d]≤d。由于最小公倍数[s,d]≥d，故[s,d]=d，这说明了s|d。
用这种证法，可以直接证明(2)，这里不作详细说明，有兴趣的读者可自行证明。
证(3)
：
显然，如果能证明(4)，那么证明多个数的情形可以化归为两个数的情形，
而这已经被证明了（第二节引理11）。
稍加改进第2节引理11的方法，再结合我们证明的(2)，可以直接完成这个证明。但如果证明(9)，那么也可以用上一节的方法。
设d=(q1,q2,…,qk)，D=(mq1,mq2,…,mqk)，我们来证明D=md。
d|q1,d|q2……可得md|mq1，md|mq2……故md|D。我们显然有m|D。则有D/m|q1,D/m|q2……可得D/m|d。此即D|md。故D=md。
证(4)
：我们只证明前者，而后者可以用类似的方法证明。(你可以试试。)
设(q1,q2,q3,…,qk)=D，(q1,q2)=d，(d,q3,…,qk)=P，要证明P=D。则P|d,d|q1,d|q2，得P|q1,P|q2。又由于P|qi(i=1,2,…,k)得到P|D。而D|qi(i=1,2,…,k)可得D|d,故D|P。因此D=P。
证(5)
：此结论于上一节已经证明。现照抄如下：
引理9
如果(a,b)=1，且a|bc那么a|c。
证：设ax+by=1，那么acx+bcy=c，由于a|acx，a|bcy故a|c
证(6)
：
设D=(a,bc),d=(a,c)，d|a,d|c得d|bc,故d|D。D|a,D|bc，设(D,b)=r，r|b,r|D有r|a，则r|(a,b)=1,故r=1。由此得D|c，所以有D|d。所以D=d
。
证(7)
：
上一节我们使用了
算数基本定理
来完成证明，这一节我们给出一个
不依赖算数基本定理
的直接证明。
设(a,b)=d，a=Ad，b=Bd。对任给的满足Ad|r,Bd|r的r,我们设r=mAd=nBd，则有mA=nB。A|nB推得A|n，同理B|m。再设n=Ak,m=Bl，则ABk=ABl推得k=l。因此n=Ak,m=Bk。则r=ABdk，显然有ABd|r。因此ABd=[Ad,Bd]。有[Ad,Bd]d=ABd^2，此即(a,b)[a,b]=ab
。
证(8)
：
这个结论已经在上一节证明了。设T中的最小正整数为d。对任意的n∈T，设n=dq+r。(0≤r＜d)。则r=n-dq，显然r∈T。因为d是r中最小正整数，故r=0。由此得d|n。由于a,b∈T，故有d|a，d|b。则d|(a,b)。可设d=ax+by，则(a,b)|a,(a,b)|b得(a,b)|d。因此我们得到(a,b)=d。
证(9)
：
由你来证明。
证(10)
：
由于d∈T，根据T的定义，这是显然的。
这启示我们：方程ax+by=(a,b)总有整数解
。
好了，现在最大公因数理论的细节彻底跟你介绍完了，感谢你的耐心理解。让我们看一个很有趣的问题
：
我国古代有过一个著名的“百鸡问题”：
“
今有鸡翁一，值钱伍；鸡母一，值钱三；鸡雏三，值钱一。凡百钱买鸡百只，问鸡翁、母、
雏
各几何
？
”
——
《
张邱建
算经》
大概意思是说
公鸡五元一只，母鸡三元一只，小鸡一元三只，问100元如何买100只鸡?
若设公鸡x只，母鸡y只，小鸡z只，则有：
x+y+z=100
5x+3y+z/3=100
消去未知数z，得到
-14x -8y = -200
,化简后得
7x + 4y = 100
这个方程未知数个数多于方程数，而且要求
整数解
，而且还要是
非负的
。应该如何解决呢？
定义6
像这样的，
未知数个数多于方程个数，解受到某些限制(通常是整数解)的方程，我们称作
不定方程
。（也叫丢番图方程。）
这一节，我们的第二件重要的事就是研究形如ax + by = c的一次不定方程。
引理15
一次不定方程ax + by = c 有整数解的充分必要条件
（注：“充分必要条件”等价于“等价于”）
为(a,b)|c。
证
：
设(a,b)=d，如果整数x,y满足方程ax+by=c，那么d|ax,d|by得d|c。
显然，ax+by=d一定有解。若d|c，则可将方程两边同乘以c/d得到(xc/d)a+(yc/d)b=c，这里
(xc/d
)，
(yc/d)都是整数。
引理15也告诉了我们，要求Ax+By=c的解首先要求Ax+By=d的解。其中d=(A,B)。记A=ad,B=bd。此时方程两边同除以d，得到ax+by=1。此时(a,b)=1，而解并没有变化。也就是说我们只要讨论(a,b)=1的情况就可以了。因此，接下来我们总假设(a,b)=1。
引理16(辗转相除法)
如果 a = bq + r，那么(a,b)=(b,r)。
证
：
设(a,b)=d,(b,r)=D，r=a-bq，那么d|a,d|b推得d|r。因此d|D。D|b,D|r推得D|a。因此D|d。因此D=d。
这是一种
不需要分解素因数
就可以求最大公因数的方法。称作“
辗转相除法
”或
Euclid算法
。
我们之前建立的理论都只能说明一次不定方程
是否可解
，但是如何来求它的解呢？假设(a,b)=1，即如何将1表示为ax+by的形式？
下面的引理回答了这个问题。
引理17
若(a,b)=1,则ax+by=1必有解。并可以通过辗转相除法求出一组解。
证
：
不妨假设a>b, 此时我们进行：
a = b×q1 + r1 (0≤r1 ＜b )
b
= r1×
q2
+ r2 (0
≤
r2
＜r1
)
r1
= r2×
q3
+ r3 (0
≤
r3
＜r2
)
r2
= r3×
q4
+ r4 (0
≤
r4
＜r3
)
r3
= r4×
q5
+ r5 (0
≤
r5
＜r4
)
……
r(n-1) = r(n)×q(n+1)+r(n+1)
由于b>r1>r2>r3>r4>r5>……>r(n+1)，余数是严格递减的，所以经过有限步骤后余数总会为0。不妨设r(n+1)=0，那么我们有：
又由辗转相除法得到(a,b)=(b,r1)=(r1,r2)=(r2,r3)=……=(r(n),r(n+1))=（r(n),0)=r(n)，又由(a,b)=1,则r(n)=1.
改写上面的式子：
r1 = a -
b×q1
r2 = b -
r1×
q2
r3 = r1 - r2×q3
……
1 = r(n-2) - q(n)×r(n-1)
我们将r1带入第二个式子，并保留ax+by的形式，然后再把r2带入第三个式子……如此不停操作，最终我们能将1表示为ax+by的形式。
引理18
如果x=X和y=Y是ax+by=1的一组解，那么ax+by=1的所有整数解为：x=X-bt,y=Y+at。t为整数。
证
：带入后显然，
x=X-bt,y=Y+at是解。我们来证明所有解都形如此。
若还有一组解x=r,y=s满足方程，那么ar+bs=1。我们有(x-r)a+(y-s)b=0，即(x-r)a=(s-y)b。由于(a,b)=1，则b|(x-r)，a|(s-y)，设x-r=bk,s-y=al，即k=l。所以r=x-bk=X-(k+t)b，s=y+ak=Y+(k+t)a。由于k+t是整数，因此这组解也是形如
x=X-bt,y=Y+at的解。
现在，我们有足够的能力来解答《张丘建算经》中的问题了，我们把这作为一个例题。
例4
求出7x+4y=100的
非负
整数解。并完整解答张丘建算经中的问题。
解：由于(7,4)=1，我们先解7x+4y=1.
7 = 4*1 + 3
4 = 3*1 + 1
所以 1 = 4 - 3 = 4 - (7 - 4) = 7*(-1) + 4*2
因此x=-1,y=2是7x+4y=1的一组解。两边同乘100，我们得到7*(-100)+4*(200)=100，因此x=-100,y=200是7x+4y=100的一组解。根据引理18，我们知道这个方程的所有解为：x=-100-4t,y=200+7t。
因此z=100-x-y=-3t，由于鸡的数量必须是非负整数，我们有：
-100 - 4t
≥
0
200 + 7t
≥
0
- 3t
≥
0
结合t也是整数，解得 -28 ≤t≤ -25，即 t = -25,-26,-27,-28.
于是我们得到这个问题的
所有解答
：
{x = 0, y = 25, z = 75}
{x = 4, y = 18, z = 78}
{x = 8, y = 11, z = 82}
{x = 12, y = 3, z = 85}
怎么样，数学的威力是不是很大？
再给你来点
练习题
：
1.证明：(a,b)=1,则(a+b,a^2-ab+b^2)=1或3.
2.证明：若a不是完全平方数那么√a 一定不是有理数。
3.证明：(a,b)=(a+b,[a,b])
4.有1美分的硬币，5美分的硬币和25美分的硬币一共10枚，它们一共恰好是1美元。问三种硬币的数量？
5.(附加题):
五
只猴子分桃子。结果发现无法均分，便不欢而散。当天晚上，一猴子悄悄前来，扔掉了一个桃子，拿走了自己的那份。过了一会，第2只猴子悄悄前来，扔掉了一个桃子，拿走了自己的那份。过了一会，第3只猴子悄悄前来，扔掉了一个桃子，拿走了自己的那份。过了一会，第4只猴子悄悄前来，扔掉了一个桃子，拿走了自己的那份。过了一会，第5只猴子悄悄前来，扔掉了一个桃子，拿走了自己的那份。最少有
__________个
桃子。
呼，终于写完这一节了，累死了，5个小时啊。。
做出来把证明回复上来，我来帮你改作业。
欢迎光临 (http://www.51hei.com/bbs/)
Powered by Discuz! X3.1