初一寒假第3讲 不定方程.doc

第三讲 不定方程不定方程定义略。我们只关心整系数不定方程的整数解。若无特殊说明，默认出现的方程是此类方程。本讲讨论几种简单而且重要的不定方程板块1 一次不定方程像ax+by=c ab0这样的不定方程叫做二元一次不定方程先给出有解条件：ax+by=c存在整数解的条件是（a，b）|c（a，b）|c不成立显然不定方程无整数解，以下证明（a，b）|c成立则方程有整数解。设a=kp b=kq c=km k=(a,b)则有(p,q)=1代入原方程，px+qy=1 我们只要证明这个方程有整数解移项得到px =1-qy ，我们只要证明p的倍数可以除以q余m即可。考虑p 2p 3p 4p 5p (q-1)p这些数，其中没有q的倍数，并且除以q余数各不相同。所以余数遍历 1,2,3q-1，其中必有p的k倍除以q余m。下面举例说明如何写出通解【例】4x+7y=1【解析】最简单易行的方法是先找到一个解。比如(2,-1)然后x的值增加7t，y的值减少4t，方程左边大小不变，等号成立。所以得到方程的参数解(x,y)=(2+7t,-1-4t) t是任意整数再举一个常数项不是1的例子。【例】31x+23y=185【解析】3123=18 18523=81我们需要8的倍数，除以23余1。24满足条件。所以原方程化为31x=23(8-y)+1 类比313=234+1得到特解x=3 8-y=4 (x,y)=(3,4)进而得到通解(x,y)=(3+23t,4-31t)其中t是任意整数【例】4x+5y=21【解析】4|5y-214|y-1y=4t+1代入得到解 其中t是任意整数三元一次不定方程的例子【例】2x+3y+7z=35【解析】观察到3y+7z是偶数也就是说y,z有相同的奇偶性设y=a+b z=a-b代入，得到参数解其中a,b是任意整数【例】2x+3y+7z=35【解析】观察到3y+7z是奇数也就是说y,z有不同的奇偶性设y=a+b+1 z=a-b代入，得到参数解其中a,b是任意整数再看三元一次不定方程组【例】【解析】把x看成常数10t，解出方程若要根是整数，t是除以4余2的。设t=4k+2，得到原方程组的解 其中k是任意整数。从上面看出，一般做法就是把其中一个未知数当成常数，把不定方程看做有唯一解的方程。求出解之后看看被当做常数的未知数必须满足什么同余条件。【例】有两堆小石子，若第一堆给第二堆100个，那么第二堆是第一堆的二倍。相反，若从第二堆拿一些放到第一堆，第一堆就是第二堆的6倍。问至少多少石子？【解析】设两堆分别是k+100,2k-100。这样就满足第一个条件。第一堆就是第二堆的6倍说明总数是7的倍数。7|k还能看出第二堆超过总数的。7(2k-100)3k 7|k满足条件的最小k是70。代入验算，满足条件。所以石子的最小数目是210下面这个结论很经典【例】a,b是大于1的两个互质整数，ax+by取不到ab-a-b，可以取到大于ab-a-b的所有整数。其中x,y是非负整数。【解析】若ab-a-b=ax+by 移项得到ab=a(x+1)+b(y+1)(a,b)=1 所以a|(y+1) y+1至少是a，这是不可能的。也就是说ab-a-b是取不到的。下面证明超过ab-a-b的任何整数都可以取到。首先，用a与若干个b凑成的不超过ab的最大整数记为。易知达不到ab，并且不小于ab-b+1。这是因为a,b互质。用2a和若干个b凑成的不超过ab的最大整数记为。同理达不到ab，并且不小于ab-b+1。同样的方法得到。这b-1个数各不相同。因为a,b互质。这b-1个数的值都取自ab-b+1，ab-b+2ab-1这b-1个数。所以这b-1个数取遍ab-b+1，ab-b+2ab-1这b-1个数。这b-1个数都至少用了一个a，所以这些数分别减去a，仍然是可以取到的。这样我们得到了ab-a-b+1，ab-a-b+2ab-a-1。还得到了ab-b+1，ab-b+2ab-1，ab。同理能得到ab-a-b+1，ab-a-b+2ab-b-1：ab-a+1，ab-b+2ab-1，ab。所以得到了ab-a-b+1到ab这些数。至于那些大于ab的数，我们可以在已经得到的数基础上，加上若干个a得到。这是因为我们得到了超过a个连续的整数。所以得不到的最大数是ab-a-b。利用这个结论看下面这道题。【例】小华玩某种游戏，每局可随意玩若干次，每次的得分是8， ，0这三个自然数中的一个，每局各次得分的总和叫做这一局的总积分小华曾得到过这样的总积分：103，104，105，106，107，108，109，110又知道他不可能得到“83分”这个总积分问：是多少?【解析】首先a应该是奇数，(a,8)=1。另外103，104，105，106，107，108，109，110都可以得到，他们是8个连续整数，所以超过102的整数都能得到。由上面结论得到 a不是15，因为155+8=83。.所以a=13。若(p,q)=1，则存在整数x,y使得px+qy=1。这个结果叫裴蜀定理。他是二元一次不定方程有解条件的特例。以下举例看看有什么用。【例】用一个19角的模具，还有一支铅笔，如何得到1的角？【解析】除了模具之外，我们还有周角=360。(19,360)=1 这就为作图创造了条件1919-360=1可见只要作19个19的角，使他们顶点重合，相邻两个角有一条公共边，那么第19个角有一个边与第一个角的一条边夹角是1。【例】m个盒子中放着若干个球，每次在其中n个盒子中加一个球（nm且m与n互质），求证一定可以在若干次操作后，使得每个盒子中的小球数目相等。【解析】因为(m,n)=1由裴蜀定理，存在正整数a,b使得an=bm+1这个式子表明每操作a次，可以使m-1个盒子分别增加b个球，另外一个盒子增加b+1个球。这样相当于我们可以把这a次操作定义为一次大操作，效果是在任意盒子里加上一个球。有了这个操作，可以在有限步之内使每个盒子中的小球数目相等。板块2 其它不定方程我们来求的正整数解。其实只要求两两互质的解。观察到x,y一奇一偶，z是奇数。不妨设y是奇数。移项得到右边是两个互质数的乘积，左边是平方数。所以右边两项都是平方数。设，得到 其中a,b一奇一偶且互质（否则不满足x,y,z两两互质）所有两两互质的勾股数组都有此形式。【例】求的正整数解【解析】首先用较小的x试验，发现x取1，2，3，4，5，6时存在明显解(x,y)=(1,1),(2,2),(4,5)对于其他情况，只要两边对4取模，能看出x应该是偶数。设x=2t，代入得到右边是连续的偶数，不全是4的倍数。所以右边的两个括号有一个是的倍数实际上时，两个括号都小于，不可能有解。所以(x,y)=(1,1),(2,2),(4,5)就是全部正整数解。【总结】这个方程从形式上看，很可能至多只对有限个正整数成立，也就是说对足够大的正整数n，方程是不成立的。所以我们采用的方法是“用大数破坏条件”。【例】x,y都是正整数，求证不能都是平方数。【解析】 化简得到化简得到所以y=2x或2x+1若y=2x，是平方数，不是平方数。若y=2x+1 不是平方数。【例】m,n都是1到99之间的整数。并且是平方数，这样的数对（m,n）有几个？【解析】这样的数对（m,n）有98个。【例】求出任何一组满足方程x2-51y2=1的自正整数解x和y。【解析】x=50 y=7满足题意【例】求方程x+y=x2-xy+y2的整数解.【解析】根据原式的对称性，设x+y=a x-y=b代入这样可以消掉xy项a,b的奇偶性是相同的（a,b）=(3,1) (3,-1) (1,1) (1,-1) (4,0) (0,0) (x,y)=(2,1) (1,2) (1,0) (0,1) (2,2) (0,0)练习题1 n50，4n+5和7n+6不互质，求正整数n。解析：（4n+5,7n+6）|7(4n+5)-4（7n+6） （4n+5,7n+6）|11如果4n+5和7n+6不互质，最大公约数只能是11。.11|4n+5解得满足条件的正整数n共有4个：7,18,29,40。2 有10个互不相同的自然数，证明他们的最小公倍数不小于最小数的10倍。解析：设这10个数是这个最小公倍数至少是的1倍，所以至少是的2倍，的3倍以此类推，至少是最小数的10倍。3 求证：两个即约分数之和是整数，那么这两个分数分母相同。解析：即约分数是整数所以b|(ad+bc)b|ad 因为（a,b）=1 所以b|d同理d|b 所以b=d4 a,b,c,d是4个正整数，并且。证明a+b+c+d是合数。解析：平方不改变奇偶性，所以a+b+c+d是个偶数。5 求证无整数解解析：平方数除以8的余数只能是0,1,4两