1、智浪教育-普惠英才文库数学奥赛辅导 第四讲 不定方程不定方程是指未知数的个数多于方程的个数,且未知数的取值范围是受某些限制(如整数、正整数或有理数)的方程.不定方程是数论的一个重要课题,也是一个非常困难和复杂的课题.1几类不定方程(1)一次不定方程在不定方程和不定方程组中,最简单的不定方程是整系数方程通常称之为二元一次不定方程 .一次不定方程解的情况有如)0,(,bacbyax下定理.定理一:二元一次不定方程 为整数.有整数解的充分必要条件是 . cbayx, cba|),(定理二:若 为之一解,则方程全部解为 . 0,1),(ba且 tytx00,(t 为整数) 。(2)沛尔 方程)(pel
2、形如 ( , 不是完全平方数)的方程称为沛尔方程 . 能够证明它12dyx*Nd一定有无穷多组正整数解;又设 为该方程的正整数解 中使 最小的),(1yx),(yxd解,则其的全部正整数解由 ( )给11 2()()nnnddyxyxy 1,23出. 只要有解 ,就可以由通解公式给出方程的无穷多组解.),(1yx 满足的关系: ; , n, 1()nndxy12nxxy(3)勾股方程 22zyx这里只讨论勾股方程的正整数解,只需讨论满足 的解,此时易知 实际1),(yxzyx,上两两互素. 这种 两两互素的正整数解 称为方程的本原解,也称为本原的勾zyx, ,z股数。容易看出 一奇一偶,无妨设
3、 为偶数,下面的结果勾股方程的全部本原解通解y公式。定理三:方程 满足 , 的全部正整数解 可表为22zyx1),(x2| ),(zyx智浪教育-普惠英才文库,其中, 是满足 一奇一偶,且22,bazybaxba, ba,0的任意整数 .1),(4不定方程 ztxy这是个四元二次方程,此方程也有不少用处,其全部正整数解极易求出:设 ,则 ,其中 ,故a),(adzc, 1),(c,1)(,dtcyta因即所以 . 因此方程 的正整数解可表示为bc则设| ztxy都是正整数,且 .反过来,易知上述datzbycx, 1),(dc给出的 都是解.t也可采用如下便于记忆的推导:设 是既约分数,即 .
4、 由于 约分后得出 ,故dcytzx这 里,1),(dczxdc,同理ac, .,abyt2不定方程一般的求解方法1奇偶分析法;2特殊模法;3不等式法;4换元法;5因式分解法6构造法(构造出符合要求的特解或一个求解的递推关系,证明解无数个)7无穷递降法由于不定方程的种类和形式的多样性,其解法也是多种的,上面仅是常用的一般方法.注:对无穷递降法的理解:以下面的问题为例:证明:方程 无正整数解。42xyz证明:假设 存在正整数解,其中 最小的解记为 。因为 ,z0z22xyz根据勾股方程的通解公式有 ,其中 一奇一偶,2220,xabyab,a。从 可以得到 为奇数, 为偶数,令 , ,,1ab2
5、x s24ybs其中 ,所以 。由 得 ,即s2,()1tsqt22x4xtq,又可以通过勾股方程的通解公式24xqt,注意到 ,所以 ,222,()lmltlml2qlm2200,lm智浪教育-普惠英才文库,而 ,与 的最小性矛盾。所以原方程组无正整数解。240tlm420ztbt0z赛题精讲例 1 (1)求不定方程 的所有解;3715xy(2)求不定方程 的所有解。92解析:(1)可以由辗转相除法得到,其实根据该方法可以得到必存在整数 ,使得,st。如 ,依次反代即可得到一个370st173,7134,81特解。(2) ,可以取 ,此时可以得到 。从而得到一个9yx502yx2y特解。注:
6、这个两个方法是基本方法。例 2求所有满足方程 的正整数解8157xyz解析:首先从同余的角度可以发现 必须为偶数, ,又 的个位数必须为8157xyz15y5,而 的个位数为 2,4,或 6, 的个位数为 3,9, 1,所以 ,对应的8x z 0,2(mod4)x。这样可以令 , ,可以得到0,2(mod)z2ykl,注意到 均为奇数,两个的和和差必定是17(175)(1)xlklkl7,5lk一个单偶,一个双偶,从而 ,目标集中于 ,观察有解312lkx12lk。当 时,两边取模 17 可以得到 矛盾。所以仅有解,1,lk2k()mod9k2例 3 为给定的一个整数,当 为何值时,方程 有正
7、整数解?有正整数aa31()yax解时,求这个不定方程。解: 可以变形为 ,这样31()yx33()x,一个明确的事实 ,从而 。这样我们3()|x 1,y31|xy得到 。不妨假设 两种情况。3|(1)|(*)yxy,(1) 智浪教育-普惠英才文库,从这个代数式发现, ,对 单独讨332211()yyay2y1论,有 , ,这种情况共有解:x,;,2xa; ,注意到*式的等价性,又有解 1,3;21aa34,9,(2) xy将等式转化为不等式 ,从同余的角度看有 ,所以321yay1,aky,321yky若 ,则 ,只能23 2 12()1 1yxyxxy是 。注意到*式的等价性,又有解 2
8、,51;,5yxaya439x综上,可以有 ,对应的解分别为,共 9 组解。3,152152,15,2例 4证明:不定方程 无整数解4xy解析: 给我们的第一个印象是 同为奇数或同为偶数。若同为偶数,则254xy,xy也就是 ,进一步有 为奇数,因为奇数的平方模 8 余 1,矛盾。3kl2518klk若同为奇数,则需进一步讨论,关键是取模为多少比较好讨论。结合费马小定理如,则 ,从而 ,但是(,1)y50(mod)yr54678(mod1)yr。比较两者我们就可以到相应的结论203,49(1)x例 5求证: 存在无数组解且每个解都大于 2009。2225xyzuvxyz证明:观察有特解 。从原
9、方程可以得到,345。这说明从一组解可以得到另一组解222()()12yzuvxyzvyzxv智浪教育-普惠英才文库。由于方程结构的对称性,不妨假设 ,则,yzuvxv 0xyzuv,主要是证明 ,这是因为 。不断yzuxvxyzuv依次类推就可得到结论。例 6 (普特南竞赛题)求方程 的整数解,其中 是质数, 是大于 1 的|1rspqqp,sr,正整数,并证明你所得到的解是全部解. 解析:容易看到两个质数中肯定有一个为 2,不妨假设 , ,即2|rs。若 ,从余数去讨论, , 为奇数。21rsq21rsq3(mod4)q,所以 ,2()rss122rrs,提取公因数,有1111()2srs
10、rsrr,从奇偶性可以看出这种情形方程无解。1111()(2)2srrsrsrs为偶数,注意到 。2rsq 12()1)rssqq, ,122rrs 11111() 2(srsrsrrrss令 , ,观察最后两uv11111() 22()srsrsrrurvv项,只能 , , ,从而1r3q3综上,考察到对称性,原方程恰有两组解:,2,23,3. .ppqqorrss例 8 (09 湖北)求不定方程 的正整数解的组数1564321 xxx解 令 , , ,则 先考虑不定方程x321 y54z6,2zy满足 的正整数解 ,53zy,z3x, x21当 时,有 ,此方程满足 的正整数解为1z63y
11、2,yx智浪教育-普惠英才文库)4,(37),210(),yx当 时,有 ,此方程满足 的正整数解为 z1yx2,3yx )2,5(,yx所以不定方程 满足 的正整数解为25z1z ),5(),4,37(),0(),(zyx又方程 的正整数解的组数为 ,方程21 xNx 21xCyx54的正整数解的组数为 ,故由分步计数原理知,原不定方程的正整数解),(xNy1Cy的组数为816930C1241321269 例 8 (09 巴尔干)求方程 的正整数解。5xyz解析:首先 , ,从而 , 为偶数。方程可31,(mod)x1(od)(mod4)x,xz以转化 , , ,25xyz25kyz35kk
12、yz35kst, 。所以 ,即得 ,下面研究352stkstz352ksttz0s215kyyz,当 时, , ,通过尝试的方法可31kyk1mod18y7od18y以得到:, , , ,在2357mod8,5od86563l6325kl考虑模 7 的余数, ,矛盾。36321(72)10(mod7)kl ll所以 ,由此可以得到方程的解为 。1,ky,xyz变式练习:(09 加拿大)已知 为完全平方数,求3ab,ab解析: 须为 4 的倍数,从而 一个为奇数,一个为偶数。37ab,若 ,则 ,同上,应该有 ,当 时,2,1kl227kbz2371kb2k, ,通过尝试的方法可以得到:0mod
13、8bod18智浪教育-普惠英才文库, 矛盾,所以 ,满足条件的 为2371mod8,71od80,1k,ab,0(2)ab仍然考虑 317kb例 9:试证:当 时,不存在 个连续自然数,使得它们的平方和是完全平方数.nn解析:设 是非负整数 .假若结论不成立 ,即存在 使x Ny即)()2()1( 22x 16ynxnx记 则).(A).(mod2A当 时,分别由 和 令 ,代入得9,43.|yz,)12(61)( 22 nnx即 .2z把 代入后将分别得到 但这是7,5n ).7(mod03)4(,5mod0)3( 22 xx不可能的,故 . 当 时,由得 1086 22)1(6)1( yxnxn若 则由知, ,由于 的任意性,所以只能有n7od2yx因此要使 成立,只能 ,于是由)7(mod42x )(m02yx )7(mod0,yx知有 ,这是不可能的,故 同理可证1316| n.6n.1n若 ,则由可得 ,这是8n )9(247981922 xyx不可能的,故 综上,命题得证.