第二章一次不定方程上述推论有许多应用，这里我们用它来获得一些求最大公因子的常用技巧推论2.2.2设a,b,cEZ，且c>0.(1)（分配律）(ac,bc)=(a,b)·c;(2)（消去律）若(a,b)=1,则(a,bc)=(a,c)(3）对任何mEZ,都有(a,b-ma)=（a.b)(4)cb当且仅当(c,b)=c.(5)设p是素数，且p+a，则(p,a)=1证明(1)设,yEZ满足ac+by=(a,b).因此(a,b)c=acr+bcyEZac.bc.由引理2.2.3(2)推知(ac, bc) / (a,b)c.另一方面，由命题2.1.1（3）及公因子的定义，我们有(a,b)c ac, (a,b)c|bc.因此由引理2.2.3(3)可知，(a,b)c|（ac,bc).这就得到(a,6)c=（ac,bc）（推论2.1.1)(2）此时aa+by=1:两边乘以c得a(ca）+bcy=c.故由引理2.2.3(2)得（a,bc)|c.显然(a,bc)|a,故(a,bc)|(a,c)。另一方面，显见(a,c)/(a,bc).这就证明了(a,bc)=(a,c)(推论2.1.1).(3)由ar+by=(a,b)得a(a+my)+(b-am)y=(a,b),故有(a,b-am)/(a,b).另一方面，显见（a,b)1（a,b一am)，这就推得等式(4)显然(5)因(p,a)|p,故由素数定义知，(p,a)=1或p.若(p,a)=p,则由(4)得p|a,矛盾！故-(p,a) = 1.例2.2.2设a=1040,b=85，求最大公因子(a,b)(a,6)=5(208,17)=5(52×4,17)=5(52,17)=5(52-17×3,17)=5(1,17)=5.事实上，这种计算方法只不过是下一节将介绍的欧几里得算法的一类特例而已，推论2.2.3设p是素数，且pab，则要么p|a，要么pb.证明由条件，(p,ab）=p.假设p+b，则由推论2.2.2（5)，(p,b）=1.进一步由推论2.2.2■(2)可得(p,a)=l，从而pta,矛盾！注2.2.4上述推论显然可以推广到更一般的情形，即若p|a1a2an，则p至少整除其中一个ai.这一推论将被用来证明正整数的素因子分解的唯一性（见算术基本定理2.3.1).2.2.2欧几里得算法这一小节将提供计算最大公因子的算法，我们考虑带余数除法a=bq1+ri,0≤ri<q1.假如r1=0,即b|a,则显然有(a,b)=b如果r1>0,则继续考虑带余数除法b=r192+r2,0≤r2<r1.依次类推，我们得到一系列-7-
第二章一次不定方程带余数除法a=bqi+ri,0≤ri<bb=r1q2+r2,0≤T2<1(2-3)0≤r3<r2r1=r293+r3,.Tn+1=0.Tn-1=Tn9n+i+Tn+l,请注意，因为余数r；是严格递减的非负整数，所以我们才能保证上面过程只能出现有限步，并且最后一式的余数是零命题2.2.1(欧几里德算法)在式(2-3）的记号下，我们有rn=（a,b)证明由推论2.2.2(3),(a,b)=(a-q1b,b)=(r1,b)。类似地，也有(r1,b)=(r2,ri)=-=(rn-1,rn).注意到rn|rn-1,故rn=(rn-1,rn)因此rn=(a,b).推论 2.2.4设q21q11-1 93 11 92 11 q4 1-1 q3 1 = (-1)n-1y=(-1)nn-1 1qn-1 1-1 qn-1 qm则 aa + by = (a,b).证明将式（2-3）写成矩阵形式（请注意最后个等式不算在内）bO9110T11 q2 1..T21 93 1::.9n-1 1.+.0-1 qnTn-1Tn由线性方程的克莱姆法则，即得111a0q211 q2 101 q3 11 93 1b.：n-1 10qn-1 1-1 Qn-1 qn-Tn上式右边等于（-1)n-1aa+（-1)nrn，左边等于（-1)nby.由此及命题2.2.1即得结论.-注2.2.5请注意，方程ar十by=（a,b)的整数解并不唯一，上面的结论只是提供了一组特解.-8-
第二章一次不定方程例2.2.3(1)设a=323,b=221,求最大公因子(a,b)及一组解(r,y)满足ar+by=(a,b).(323=221×1+102221=102×2+17102=17×6.因此（a,6)=17.由推论2.2.4，可取=-2,y=3.(2)设a=169,b=121,求最大公因子(a,6)及组解(a,y)满足ar+by=(a,b)169=121×1+48121 =48×2+2548=25×1+2325 = 23 × 1 + 223 = 2 × 11 + 12=1×2-因此（a,6)=1.由推论2.2.4,可取=58,9=81.2.3算术基本定理2.3.1算术基本定理现在我们要利用推论2.2.3来证明素数分解的唯一性，这就是如下的经典结论定理2.3.1（算术基本定理）-任何大于1的正整数都有唯一的素因子分解，即它的标准分解式是唯一的确定的证明由命题2.1.2.我们已经知道任何正整数n1都可以分解成素数之积.现在我们要证分解的唯一性，假设n有两种标准分解式n=pnpa..pn=qmqm2.qm,P<p2<.<ps,q<q2<.<qt此处pi,qi皆素数对每个qi，因为qiIpnpaa..pra故由推论2.2.3可知i必定整除某个pj：又因为qi;Pi都是素数，所以这就迫使i=pi:因此(q1,*,qt) C (P1,ps].同理可证[p1,., ps) c(q1+qt].从而两个集合相等，并且由序关系可知s=t，pi=i（i=1,，s)这样，我们有pnp2a..pn=pmpm..pma.如果对某个i有ni>mi，则上式两边同时除以pm，则右端不含因子pi，故不被pi整除；而左端却包含pni-m，矛盾！因此ni≤m对任何i都成立.同理亦可证ni≥mi，这就推出ni=mi.■-9-
第二章一次不定方程2.3.2应用(I)：最大公因子的素因子分解算法有了算术基本定理，我们就可以用标准分解式来计算最大公因子：不妨设a，b>1是正整数它们的素因子分解中可能会出现这样一类情况：α含有素因子p，但b不含p.此时为方便讨论，我们可以在b的素因子分解中添入po项，这样至少在形式上，a.b的分解式中都出现p.因此我们不妨在此意义上考虑“广义”的标准分解式 a = pr!..- p., Qi ≥0,(2-4)I b = p...- ., βi ≥0.推论2.3.1在上述记号与假设下，我们有(a,b) = Pi...-p.,这里%=min(ai,B),i=1,..，8.证明设c=p..p由的定义na==ppi-n..= -,p3-%C都是整数，并且每个pi不可能同时出现在%，负中：因而（%，）=1.由推论2.2.2（1)，这就推出-(a, b) = d(%, ) = d.例2.3.1(1)设a=12,b=18,求(a,6)考虑素因子分解a=22.3,b=2l.32由推论2.3.1即得(a,6)=21.31=6.(2) 设a = 162,b = 98,求(a,b)考虑素因子分解a=2.34=21.34.70,b=2l.72=21.30.72-我们有（a,6)=21.30.70=2我们现在有两种方法计算最大公因子：欧几里德算法和素因子分解方法．第一种方法无需了解整数的素因子是什么，只需要简单的带余数除法即可求出最大公因子：而第二种方法却必须先知道每个整数的素因子分解式.通常来说，求一个大整数的素因子分解往往是非常困难的，其计算量可能极其巨大，因此用后一方法具体计算大整数的最大公因子实际上意义并不大2.3.3应用(II)：最小公倍数的素因子分解算法定义2.3.1设a,b,cEZ，ab≠0.如果c满足ac,bc，我们就称c是a,b之公倍数.a,b所有公倍数中的最小正数者称为最小公倍数，记作lcm(a,b)，或简记为[a,b]类似公因子，我们可以用方程的语言重新叙述公倍数的定义，即如果方程组[ ar = c,Lby=c- 10 -
第二章一次不定方程有整数解（a,y)，则称c为a,b之公倍数我们也可以归纳定义n个整数a1，.，an的公倍数和最小公倍数[a1,**: ,an] - [a1,..,an-i], an]推论2.3.22在式(2-4)的记号与假设下，我们有[a, b] = ..- .,.这里,=max(αi,β;)，i=1，.，8.特别地，任何公倍数都能被[a,b]整除证明设c=pi.po由;的定义，显然有a|c,b|c.假设d是a,b的公倍数，则d的-素因子分解中p;的方幂不小于8,=max(ai,β:)，因而c|d.这也蕴含着c=[a,b]例2.3.2(1)设a=12,b=18,求[a,b]考虑素因子分解a=22.3,b=21.32由推论2.3.2即得[a,]=22.32=36(2) 设a = 162,b = 98, 求[a,b].考虑素因子分解a=234=21.34,70,b=21.72=21.30.72-我们有（a,6)=21-34.72=7938与求最大公因子一样，用素因子分解方法来求最小公倍数往往计算量很大，下面的推论可以将最小公倍数计算归结到最大公因子计算，从而可以用欧几里得算法有效地计算推论2.3.3对任何正整数a,b，我们有恒等式(a, b) -[a,b] = ab证明在式（2-4)，推论2.3.1和推论2.3.2的记号与假设下，我们有(a,b) [a,] = p7+1 -+.-注意到%+5;=min(ai,B）+max(ai,β）=α+βi，因此上式就等于ab例2.3.3设a=6b=15,c=20.求a,b,c的最大公因子和最小公倍数因 (a,6)=3, 故(a,b,c)= ((a,b),c)= (3,20)= 1.-因[a,] = = 30, 故[a,b, = [a,6], = [30, 20] = 60.2.3.4应用(III)：一些无理数的判定这一节中，我们利用算术基本定理来证明一些实数的无理性推论2.3.4（毕达哥拉斯）V2是无理数，即V2±Q，-11 -