高中数学竞赛辅导-初等数论(不定方程)

数学奥赛辅导第四讲不定方程不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题.1．几类不定方程（1）一次不定方程在不定方程和不定方程组中，最简单的不定方程是整系数方程)0,0(,0bacbyax①通常称之为二元一次不定方程.一次不定方程解的情况有如下定理.定理一：二元一次不定方程cbacbyax,,,为整数.有整数解的充分必要条件是cba|),(.定理二：若00,,1),(yxba且为①之一解，则方程①全部解为atyybtxx00,.（t为整数）。（2）沛尔)(pell方程形如122dyx（*dN，d不是完全平方数）的方程称为沛尔方程.能够证明它一定有无穷多组正整数解；又设),(11yx为该方程的正整数解),(yx中使dyx最小的解，则其的全部正整数解由111111111[()()]21[()()]2nnnnnnxxdyxdyyxdyxdyd（1,2,3,n）给出.①只要有解),(11yx，就可以由通解公式给出方程的无穷多组解.②nnyx,满足的关系：11()nnnxydxyd；11211222nnnnnnxxxxyxyy，（3）勾股方程222zyx这里只讨论勾股方程的正整数解，只需讨论满足1),(yx的解，此时易知zyx,,实际上两两互素.这种zyx,,两两互素的正整数解),,(zyx称为方程的本原解，也称为本原的勾股数。容易看出yx,一奇一偶，无妨设y为偶数，下面的结果勾股方程的全部本原解通解公式。定理三：方程222zyx满足1),(yx，2|y的全部正整数解),,(zyx可表为2222,2,bazabybax，其中，ba,是满足baba,,0一奇一偶，且1),(ba的任意整数.4．不定方程ztxy这是个四元二次方程，此方程也有不少用处，其全部正整数解极易求出：设azx),(，则adzacx,，其中1),(dc，故1),(,,dcdtcyadtacy因即，所以bctbtyyd则设,,|.因此方程ztxy的正整数解可表示为dcbabctadzbdyacx,,,.,,,都是正整数，且1),(dc.反过来，易知上述给出的tzyx,,,都是解.也可采用如下便于记忆的推导：设dcdcytzx这里,是既约分数，即1),(dc.由于zx约分后得出dc，故adzacx,，同理.,abycbt2．不定方程一般的求解方法1．奇偶分析法；2．特殊模法；3．不等式法；4．换元法；5．因式分解法6．构造法（构造出符合要求的特解或一个求解的递推关系，证明解无数个）7．无穷递降法由于不定方程的种类和形式的多样性，其解法也是多种的，上面仅是常用的一般方法.注：对无穷递降法的理解：以下面的问题为例：证明：方程442xyz无正整数解。证明：假设442xyz存在正整数解，其中z最小的解记为0z。因为22222xyz，根据勾股方程的通解公式有2222220,2,xabyabzab，其中,ab一奇一偶，,1ab。从222xab可以得到a为奇数，b为偶数，令2bs，224yabas，其中,1as，所以22,,(,)1atsqtq。由222xab得2444xtq，即2444xqt，又可以通过勾股方程的通解公式222222,22,,(,)1xlmqlmtlmlm，注意到2qlm，所以2200,llmm，24400tlm，而420ztbt，与0z的最小性矛盾。所以原方程组无正整数解。赛题精讲例1．（1）求不定方程3710725xy的所有解；（2）求不定方程719213xy的所有解。解析：（1）可以由辗转相除法得到，其实根据该方法可以得到必存在整数,st，使得371071st。如10723733,371334,3481，依次反代即可得到一个特解。（2）213197yx，可以取353027yxy，此时可以得到2y。从而得到一个特解。注：这个两个方法是基本方法。例2．求所有满足方程81517xyz的正整数解解析：首先从同余的角度可以发现y必须为偶数，81517xyz，又15y的个位数必须为5，而8x的个位数为2，4，或6，17z的个位数为3，9，1，所以0,2(mod4)x，对应的0,2(mod4)z。这样可以令2yk，2zl，可以得到2281715(1715)(1715)xlklklk，注意到17,15lk均为奇数，两个的和和差必定是一个单偶，一个双偶，从而311715217152lklkx，目标集中于17152lk，观察有解,1,1lk。当2k时，两边取模17可以得到(1)2mod9k矛盾。所以仅有解2,2,2例3．a为给定的一个整数，当a为何值时，方程31(1)yaxy有正整数解？有正整数解时，求这个不定方程。解：31(1)yaxy可以变形为333331(1)xyyxyaxy，这样333(1)|xyyxy，一个明确的事实31,1xyy，从而3(1)|1xyx。这样我们得到33(1)|1(1)|1(*)xyxxyy。不妨假设,yxyx两种情况。（1）yx3322111(1)11yyayayyy，从这个代数式发现，2y，对1y单独讨论，有2(1)ax，1,3;2,2axax，这种情况共有解：1,3,1;22,1aa；32,2a，注意到*式的等价性，又有解14,1,3;91,2aa（2）xy将等式转化为不等式321111yayyy，从同余的角度看有1,1akyk，所以3211111ykyyyy，若1k，则232121(1)(1)1111yyyxyyxyxxyyy，只能是2,5,1;3,5,2yxayxa。注意到*式的等价性，又有解5,2,14;5,3,9yxayxa综上，可以有1,2,3,9,14a，对应的解分别为3,15,22,11,23,52,21,35,32,5共9组解。例4．证明：不定方程254xy无整数解解析：254xy给我们的第一个印象是,xy同为奇数或同为偶数。若同为偶数，则254324kl也就是2518kl，进一步有k为奇数，因为奇数的平方模8余1，矛盾。若同为奇数，则需进一步讨论，关键是取模为多少比较好讨论。结合费马小定理如(,11)1y，则5110(mod11)yor，从而54678(mod11)yoror，但是20,1,3,4,5,9(mod11)x。比较两者我们就可以到相应的结论例5．求证：2222265xyzuvxyzuv存在无数组解且每个解都大于2009。证明：观察有特解1,2,3,4,5。从原方程可以得到22222()()12yzuvxyzuvyzuvxyzv。这说明从一组解可以得到另一组解,,,,yzuvxyzuv。由于方程结构的对称性，不妨假设0xyzuv，则yzuvyzuvx，主要是证明vxyzuv，这是因为vxvxyzuv。不断依次类推就可得到结论。例6．（普特南竞赛题）求方程||1rspq的整数解，其中qp,是质数，sr,是大于1的正整数，并证明你所得到的解是全部解.解析：容易看到两个质数中肯定有一个为2，不妨假设2p，|2|1rsq，即21rsq。若21rsq，从余数去讨论，3(mod4)q，s为奇数。1221(1)(1)rsssqqqq，所以12121212rrssqqq，1111(1)2211222srsrsrrrss，提取公因数，有1111(1)(2)2211222srrsrsrrss，从奇偶性可以看出这种情形方程无解。21rsq为偶数，注意到1221(1)(1)rsssqqqq。12121212rrssqqq，11111(1)21221122(1)22srsrsrrrrssss，令2usv，11111(1)21221122(1)22srsrsrrurrusvsv，观察最后两项，只能11r，3q，2s，从而3r综上，考察到对称性，原方程恰有两组解：3,2,2,3,2,3,3.2.ppqqorrrss例8．（09湖北）求不定方程21533654321xxxxxx的正整数解的组数．解令xxxx321，yxx54，zx6，则1,2,3zyx．先考虑不定方程2153zyx满足1,2,3zyx的正整数解．1,2,3zyx，123215yxz，21z．当1z时，有163yx，此方程满足2,3yx的正整数解为)4,4(),3,7(),2,10(),(yx．当2z时，有113yx，此方程满足2,3yx的正整数解为)2,5(),(yx．所以不定方程2153zyx满足1,2,3zyx的正整数解为)2,2,5(),1,4,4(),1,3,7(),1,2,10(),,(zyx．又方程)3,(321xNxxxxx的正整数解的组数为21xC，方程yxx54)2,(xNy的正整数解的组数为11Cy，故由分步计数原理知，原不定方程的正整数解的组数为81693036CCCCCCCC1124132312261129．例8．（09巴尔干）求方程235xyz的正整数解。解析：首先31,3(mod4)x，51(mod4)y，从而31(mod4)x，,xz为偶数。方程可以转化235xyz，2235kyz，(3)(3)5kkyzz，3535ksktzz5532552stkstz，2355552ksttsz。所以0s，即得2315512kyyz，下面研究2315ky，当2k时，150mod18y，517mod18y，通过尝试的方法可以得到：2357mod18,51mod18，651mod18，63yl，632315kl，在考虑模7的余数，636363323151(72)12120(mod7)klll，矛盾。所以1,1ky，由此可以得到方程的解为2,1,2xyz。变式练习：（09加拿大）已知37ab为完全平方数，求,ab解析：37ab须为4的倍数，从而,ab一个为奇数，一个为偶数。若2,21akbl，则2237kbz，同上，应该有2371kb，当2k时，710mod18b，717mod18b，通过尝试的方法可以得到：23713mod18,71mod18，矛盾，所以0,1k，满足条件的,ab为,0,1(2,1)ab仍然考虑2317kb例9：试证：当112n时，不存在n个连续自然数，使得它们的平方和是完全平方数.解析：设x是非负整数.假若结论不成立,即存在Ny使,)()2()1(2222ynxxx即22)12)(1(61)1(y