第二章一次不定方程证明考虑方程（2-9)的整数解通解公式a= ao +bt, y= yo- at.(1)假设n>ab-a-b.由带余数除法，我们可取t使得0 ≤ yo - at <a从而0≤yo-at≤a-1.因此(ro+bt)a= n-b(yo-at) >ab-a-b-b(a-1)=-a故o+bt>-1,从而ro+bt≥0.这样，我们就得到一组非负整数解(2)假设n=ab-a-b,则方程(2-9)可写为ab = (α + 1)a + (y + 1)b因（a,6)=1.所以这就推出a/ (y+1),b/(a+1)如果≥0≥0,则+1≥b,y+1≥a,从而ab=(α+1)a+(y+1)b≥2ab.矛盾！因此此时方程无非负整数解图命题2.4.3设a,b是正整数，Cn是不定方程aa十by=n的非负整数解的个数，则我们有以下幂级数展式1cnzn(1 - 2a)(1 - z6)m-0例2.4.2上述命题可以用来具体求解方程(2-9)的非负整数解个数.这里举一个简单的例子.考虑方程&十2y=n.注意到111112(1 - z)2(1 -z)(1 -z2) ((1 - 2)2(1 + z)4(1 -2)4(1 +z)因此幂级数展开上式可求得的系数为n+1(-1)n1Cn=4+24.另一方面，我们也可以直接从方程得到cn=[]+1.2.4.2多元一次不定方程的求解算法我们考虑不定方程(2-11)airi+..+anan=M的整数解（a1,,an)，这里诸a和N是整数.定理2.4.1不定方程(2-11)有整数解的充分必要条件是(ai,...,an)IN证明设d=(a1,...,an)-17-
第二章一次不定方程(一）如果不定方程(2-11）有整数解（at1，：，n)，则由整除的加性性质可知d aiai+..+anan=N.(一）今假设d|N，我们要证方程（2-11)有整数解对n施归纳法.n=1,2时结论已证(见命题2.4.1)．今假设<n的情形已证.设d=（a1，，an-1).由最大公因子定义，(d,an）=d.由命题2.4.1,因d|N，故存在整数对（y,an）满足d'y+anan=N又由归纳假设，存在整数组（c1,.…：，an-1)，满足aizi +...+an-1an-1= d'y-因此（a1,.，an）满足方程(2-11)注2.4.1我们记(ai,..,an)=(airi+...+antn|ri,..,an EZ)它称之为整数集Z中由a1，.，an生成的理想.由一个整数生成的理想称为主理想.定理2.4.1就是说(al, ,an)= (d)■这里d=（a1,.,an).因此Z中任何理想都是主理想定理2.4.1提供了一种计算多元一次不定方程的归纳性解法.这里我们以三元一次不定方程ar+by+cz=n为例，来总结一下求解方法，(1）先判断(a,b,c)n，然后将方程化简为(a,b,c)=1的情形(以下各步均作此假设).(2)设d=(a,b)，先求辅助方程ar +by = d的特解（10,30).(3)再求辅助方程dw+cz=n的一组特解（wo,zo)（4）原方程通解(= ao(wo+ ct)+sy = yo(wo + ct) -gs,(2= 20-dt,这里t，跑遍所有整数.请注意，一般说来，通解公式的表达式不唯一，这取决于参数的选取例2.4.3求方程4+6y+12z=28的所有整数解，以及它的所有正整数解因为（4.6.12）=2|28.所以方程有解，且可简化为2a + 3y + 6z = 14.先求辅助方程2r +3y = 1-18-
第二章一次不定方程的特解（ao,o）=（-1,1).再求辅助方程w+6z=14的一组特解（wo,zo）=(2,2).这就得到原方程组的通解公式a = -2- 6t + 3s,y = 2+6t-28,2=2-t,这里t，s跑遍所有整数.如果a，y，之皆正整数，则得不等式-2-6t+3s>0,2+6t-28>0,2-t>0.因为t,s取整数，所以只能有(t,s）=(1,3)，从而（,y,2)=(1,2,1)类似二元一次方程情形，我们也关心多元一次不定方程的非负整数解情形。比如能否求出最大的正整数不能由ar+ by +cz表出者（(a.b.C是互质的正整数）？这是至今未能彻底解决之难题.又比如多元一次不定方程的非负整数解数是多少？（二元情形可精确求之，亦可见习题2.8之近似解答）.仿照命题2.4.3，我们有引理 2.4.1设a1,a2，,an皆正整数，且（a1，，an）=1，A(N）是方程（2-11)的非负整数解的个数，那么1ZA(N)eN.(1 - 201)(1 202) ... (1 - 20)N=0对具体的方程，A(NV）可以利用幂级数展开求得．具体言之，我们设1, S1, S2,*St是方程（1一2)(1－22)(1－≥）=0的所有不同的根，它们的重数分别是n,l1,l2.*..,ln因为（a1,,an）=1,所以诸li≤n-1由分部分式法得1(1 - 2a1)(1 - 2a2) .-- (1 - 24m)BtBiArA1(2-12)(1 - z)n(1 2)(G1 - 2)4((1 - 2) Ci.C1(St - 2)(St - 2)注意到A(a-a-19-
第二章一次不定方程的幂级数展开中N的系数AA.(2-13)(N) =Q+N这样，我们就可以求出A(）的精确表达式例2.4.4用上述方法可求得方程a+2y+3z=n的非负整数解个数等于(n + 3)2 _ 7 + (-1) + 2 cos2nT-cos72712893-具体验证留给读者有时候我们并不需要求A(N）的精确式，而只是希望估计A(V）定理2.4.2在引理2.4.1的条件下，我们有1A(N)limN-00 Nn-1aia2...an (n-1))证明在式(2-13)中取α=S,=li，则由αl=1及1≤n-1推知(N)lim=0N=0o Nn-1同理，如取α=1,1<n，上面的极限式也成立，因此AnA(N)limN=00 Nn-1:(n - 1)这里An是分部分式(2-12)中(1-2)-n的系数。由简单计算可知1(1z)nAn = lm (1- 2)...(1 - 2m)ai-.-an这就证明了结论，■2.5同余式在很多涉及带余数除法的问题中，我们主要关心余数，而对商并不太关心，类似地，在一次不定方程中，我们主要关心特解，因为通解很容易从特解求出，因此我们可以引进一种便捷的记号一同余，省略掉那些不太重要的信息，进一步突出我们所要关心的对象，2.5.1同余与完全剩余系定义2.5.1设a,b,mEZ，且m>0.如果ml(a-b)，则称a与b对模m同余(Congru-ent)，记为a=b(modm)反之，如果mt(a-b)，则记a丰b(modm）引理 2.5.1设b=mq2+r2，a=mqi+ri,0≤r1,r2<m是带余数除法，则a=b(modm）当且仅当r1=r2- 20 -
第二章一次不定方程证明由(a-b)=m(q1-q2)+(r1-r2)，我们有a=b (mod m)mla-bm|ri-r2.注意到0≤r1一r2l<m所以上面的最后一个条件m|r1r2也等价于r1=r2■例2.5.1(1)31=-9(mod10).这等价于说10|31-(-9)-(2)a=b(mod 1),对任何a,beZ成立.命题2.5.1同余关系是等价关系，即满足以下三条性质：(1)（自反性）a三a(modm).(2）（对称性）a三b（modm)，则b三a（modm)(3)(传递性)若a=b (mod m)且b=c (mod m),则 a=c (mod m)-证明由引理2.5.1立得我们考虑集合0=mq+o qeZ)=(a|a=0 (mod m)),1=[mq+1 /qeZ)= a|a=1 (mod m)),::T=(mq+r|qeZ)=a|a=r(modm))目三m-I= [mq+m-1lqEZ)=[a[a=m-1 (mod m)这些集合0,.，m-1称为模m的剩余类.所有剩余类的全体称作完全剩余系，记作Zm.注2.5.1有时为方便起见，我们也可以把剩余类a中的任一元素一比如b，挑出来作为代表元，记作6.它和a指代同一个剩余类.比如模2的剩余类中，1和3是同一个剩余类，都表示全体奇数构成的集合；0和2指同一剩余类，即全体偶数构成的集合。显然0i构成完全剩余系Z2.推论2.5.1模㎡的剩余类恰好是同余关系诱导的等价类：换言之，它们满足以下性质：(1)a=b当且仅当a=b(modm).(2)若ab, 则anb= 0.(3) Z=OUIU...Um-1.证明（1）由引理2.5.1及定义即知(2）若存在aEanb,则由定义知a三a（modm）,a=b（modm），由传递性立得a=b(modm)，矛盾！■(3)对任何整数a,考虑带余数除法a=mg+r,0<≤r<m.因此aEr命题2.5.2设a1=bl (mod m),a2=b2 (modm),则(1）（保加减运算）ai±a2=b1±b2（modm).(2）（保乘法运算）aia2三bib2（modm)(3）（保互质性）若（a1,m）=1,则必有（b1,m）=1- 21 -