数学奥赛辅导 第四讲不定方程知识、方法、技能不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题.Ⅰ. 几类不定方程 1．一次不定方程在不定方程和不定方程组中，最简单的不定方程是整系数方程)0,0(,0≠>=++b a c by ax通常称之为二元一次不定方程. 一次不定方程解的情况有如下定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. ① 【证】必要性 设00,y x 是①的解，则有c by ax =+00. 设.|,|,|),,(00c d by d ax d b a d 所以有则有= 充分性 设),(b a d =且c d|，有d c c 1=.因),(b a d =，则存在00,y x ，使得00by ax d +=，于是有,01011y c b x c a d c c ⋅+⋅== 所以0101,y c x c 是①的解.显然，当方程①有解时，c d |. 则用d 去除①的两端有111c y b x a =+ ②此时，1),(11=b a 且②与①同解，因此，我们只须讨论1),(=b a 时方程①的解.定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）.【证】设00,y x 为①的一解，则有c by ax =+00 ③设y x ,是①的任一解. 用①式减去③式有0)()(00=-+-y y b x x a .因为,1),(=b a 于是有)(|0x x b -，即.0bt x x =-从而有.0bt x x +=将此结果代入上式得at y y -=0.即方程任一解都可以表示为t at y y bt x x (,00-=+=为整数）.反之，若00,y x 是①的解，则容易验证at y y bt x x -=+=00,均是①的解. 从而定理得证.2．沛尔)(pell 方程二元二次不定方程本质上归结为（双曲型）方程c dy x =-22 ④的研究，其中c d ,都是整数，0>d 且非平方数，而0≠c .方程④的一个特殊情形122=-dy x ⑤最为重要，也最为基础，这称为沛尔方程. 能够证明（本书不予讨论）方程⑤一定有无穷多组正整数解；又设),(11y x 是⑤的正整数解),(y x 中使d y x +最小的解，则⑤的全部正整数解由⎪⎪⎩⎪⎪⎨⎧--+=-++=])()[(221])()[(2111111111n n n n n y d x y d x y y d x y d x x ⑥ 给出.（n =1，2，…）读者不难由⑥导出n n y x ,满足的线性递推关系⎩⎨⎧-=-=----2112112,2n n n n n n y y x y x x x x ⑦ 沛尔方程在数学竞赛中主要用于证明问题有无穷多个解，实际上对具体的d ，可用尝试法求出⑤的一组正整数解),(11y x （因为方程一定有解！），无论),(11y x 是否为基本解，由⑥均给出方程的无穷多组解.3．勾股方程222z y x =+这是一个相当特殊的三元二次不定方程，它有鲜明的几何意义，并应用广泛.这里只讨论勾股方程的正整数解，由方程不难看出，如果d y x =),(，则22|z d ，从而z d |，这样可在勾股方程的两边约去2d . 所以我们只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数.将方程模4，并注意1),(=y x ，可知y x ,一奇一偶，无妨设y 为偶数，下面的结果给出了勾股方程的全部本原解.定理三：方程222z y x =+满足1),(=y x ，y z |的全部正整数解),,(z y x 可表为2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且1),(=b a 的任意整数. 证明从略.4．不定方程zt xy =这是个四元二次方程，此方程也有不少用处，其全部正整数解极易求出：设a z x =),(，则ad z ac x ==,，其中1),(=d c ，故1),(,,===d c dt cy adt acy 因即， 所以bc t bt y y d ==则设,,|. 因此方程zt xy =的正整数解可表示为d c b a bc t ad z bd y ac x ,,,.,,,====都是正整数，且1),(=d c .反过来，易知上述给出的t z y x ,,,都是解.也可采用如下便于记忆的推导： 设dcd c y t z x 这里,==是既约分数，即1),(=d c . 由于z x 约分后得出d c ，故ad z ac x ==,，同理.,ab y cb t ==Ⅱ. 不定方程一般的求解方法 1．奇偶分析法； 2．特殊模法； 3．不等式法； 4．换元法.由于不定方程的种类和形式的多样性，其解法也是多种的，上面仅是常用的一般方法.赛题精讲例1：求方程5||=-s r q p 的整数解，其中q p ,是质数，s r ,是大于1的正整数，并证明你所得到的解是全部解. （第37届美国普特南数学竞赛试题）【解】由p 和r q ,和s 的对称性，不妨设s r q p >，即不妨只考试方程1=-s r q p ①的整数解p ，r q ,，s 仍如题设）. 显然，①中q p ,不能全为奇质数，且q p ≠，故q p ,中恰有一个等于偶质数2.（1）若2=p ，此时设.121+=q q 如果12s s =是偶数，则k k q q s s (421)12(1121+=++=+为正整数）不能被4整除，而)1(2>=r p r r 能被4整除，①不成立，故s 只能取奇数值.于是3≥s ，此时，)1)(1(1221+-+-+=+==--q q q q q p s s s r r ，故1+q 只含素因子2.设)2(21≥=+t q t，则).2(21)12(122 +⋅-=+-=+=t C s q s t s t s r由于)2(2 +⋅-t C s s 与s 的奇偶性相同，即为奇数，故只能等于1，这样一来r t =，从而方程①1)12(2=--sr r ，得1=s ，这与题设1>s 矛盾，故①中p 不能取值2.（2）若2=q ，则由①得)1)(1(1221+++-=-=-- r r r s p p p p ，故1-p 只含素因子2.设11,0(2),1(21r u r r t p ut≥⋅=≥=-为奇数),则)2)1((21)12(2111 +⋅-+=-+=-+t u t r t s r r r ,若2≥t ,则 +⋅-+-1112)1(t r r r 是大于1的奇数,上式不能成立,故1=t ,即.3=p 这时由方程①得.14)1(4)1()1(1)14(13222111-+⋅-+⋅-+-=--=-=-- r r r r r r r s C C若r 是奇数，显然上式不成立；若4≥r 是偶数，则上式右边等于－4r +8r （r －1）－…=－4r [1－2（r －1）+…]，而[1－2（r －1）+…]不是偶数，因而只能等于－1，故,4132r r s =-=显然4≥r 时此式不成立，于是2=r ，进而由81322=-=s 得s =3，从而方程①的解只能是.3,2,2,3====s r q p综上，考察到对称性，原方程恰有两组解：⎪⎪⎩⎪⎪⎨⎧====⎪⎪⎩⎪⎪⎨⎧====.2,3,3,2.3,2,2,3s r q p s r q p 例2：试证：当112<<n 时，不存在n 个连续自然数，使得它们的平方和是完全平方数. 【证明】设x 是非负整数.假若结论不成立,即存在N y ∈使,)()2()1(2222y n x x x =++++++ 即22)12)(1(61)1(y n n n x n n nx =+++++ ①记).12)(1(61++=n n n A 则).(mod 2n A y ≡当9,4,3=n 时，分别由① 和.|y n 令nz y =，代入①得,)12)(1(61)1(22nz n n x n x =+++++即.)1(121)21(222nz n n x =-+++把7,5=n 代入后将分别得到).7(mod 03)4(),5(mod 02)3(22≡++≡++x x 但这是不可能的，故7,5≠n .当10,8,6=n 时,由①得222)]12(61)[1(y x n n nx x n +=++++ ② 若,6=n 则由②知,)7(mod 022≡+y x ，由于x 的任意性，所以只能有)7(mod 40,2,1,02≡x 因此要使)7(mod 022≡+y x 成立,只能)7(mod 0,0≡≡y x ,于是由③知有137)12)(1(61|72⨯=++n n n ,这是不可能的,故.6≠n 同理可证.10≠n若8=n ,则由②可得)9(mod 6204179861989222≡≡⨯⨯⨯+⨯+=+x x y x ,这是不可能的,故.8≠n 综上,命题得证. 【评述】11=n 时,有.1434839382222=+++例3：试求所有的正整数n ，使方程222333z y nx z y x =++有正整数解.(1987年中国国家队选拔考试题)【解】设z y x ,,为其正整数解,由对称性,不妨设z y x ≤≤.显然，,|332y x z +故.332y x z +≤但2323,yz y xz x ≤≤，因而),(2223322y x y nx y x y nx z +-≥+-=故 .)]([222233y x y nx z y x +-≥≥+ 于是,)(23322442y x y x y nx y x n +++≤.11)11(233nynx y x xy +++<易知1=n （否则，若2≥x ，则上式端不小于4，右端不大于3，矛盾），这样上式转化为.1223nyy y ++<此式只有3≤y 时才能成立.当注意到332|y x z +，即.1|32y z +因此，只能是1,1==z y 或2,3(3,2====z y z y 时不合y z ≥）.把所得的解代入原方程就可得3=n 或1. 例4：在无限方格纸（方格的边长为1）上仅可沿网格线作划分，求证：对于任一整数12>m ，可以划分出这样的矩形，它的面积大于m ，而从其中不可能再分出面积等于m 的矩形. (1985年第19届全苏数学竞赛试题)【证明】设某一矩形边长为.*,N y x ∈不失一般性,设y x ≤.由题意，x 、y 应满足：.)1(,)1(,m y x m y x m xy <-<->但由于y x ≤知)1()1(-≤-y x y x ,于是只要证明不等式组：y x m y x m xy ≤<->,)1(, ①有正整数解就可以了.由于对任一正整数m ，必定有*)()1(22N k k m k ∈+<≤，所以可分下面四种情形讨论： （1）当2k m =时，①有解;2,1+=-=k y k x （2）当)1(2+<<k k m k 时，①有解;1,+==k y k x （3）当)1(+=k k m 时，①有解;3,1+=-=k y k x（4）当2)1()1(+<<+k m k k 时，①有解.1,1+=+=k y k x例5：求方程7322=+-+yxy x y x 的所有整数解. (1986年第12届全国数学竞赛试题)【解】因为].)(3)[(412222y x y x y xy x -++=+-若令,,q y x p y x =-=+则原方程可化为).3(32822q p p +=由此可看出0>p 且p 是3原倍数.设,3k p =其中k 是正整数，则)3(32822q p p +=，于是0>k 且k 是3的倍数.设m k 3=（其中)N m ∈，则.272822q m m +=再由0272822≥=-q m m 知1=m .此时，1,9,3±===q p k ，故可由方程组⎩⎨⎧±=-=+.1,9y x y x 解得原方程的整数解).5,4(),4,5(),(=y x例6．求方程!!!!z y x W ++=的所有正整数解.(1983年加拿大数学竞赛题)【解】由对称性,不妨设z y x ≤≤.显然1+≥z W ，于是,!3!!!!)!1(z z y x W z ≤++=≤+ 即,!3)!1(z z ≤+于是.2,31≤≤+z z 由z y x ≤≤知， （1）2,2,2===x y z 时，;3=W （2）1,2,2===x y z 时，W 无解；（3）1,1,2===x y z 时，W 无解；（4）1,1,1===x y z 时，W 无解；于是原方程只有一组正整数解：2,2,2===z y x ，.3=W【评述】建立“递推关系”也是解竞赛题的一种常用技巧.对于不定方程,如果能建立未知数的某种递推关系,并且再知一组简单解(相当于递推数列中的初始值),那么,就可以通过递推关系得到所有解,请看例7.例7：确定22n m +的最大值.其中m 、n 为整数，且满足：m 、n .1)(},1981,,2,1{222=--∈m mn n ①（第22届IMO 试题）【解】只需找到适合①的最大m 、n ，由122±=--m mn n 可得.1222m mn m n ≥±+=因m 、n 为不大于1981的正整数，因此有m n ≥，当且仅当1==n m 时等号成立.显然1,1==n m 是①的一组解.当1,1≠≠n m 时，0>-m n ，且有（递推关系）：.])()([])()[()(222222222m n m n m m m m n m m n m mn n ----=--+-=--于是，若（n m ,）是①的一组解，那么（m m n ,-）也是①的一组解.由于m n >，则可从（m n ,）出发，递降得到（1，1）.反之,亦成立.即由解（1，1）出发，利用从（m m n ,-）→（m n ,）可得到满足}1981,,2,1{, ∈n m 的全部解.即 （1，1）→（1，2）→（2，3）→（3，5）→（5，8）→（13，21）→（21，34）→（34，35）→（55，89）→（89，144）→（144，233）→（233，377）→（377，610）→（610，987）→（987，1579）. 因此,所求的22n m +的最大值为.3524578159798722=+ 例8：证明：有无穷多个正整数,n 使得]2[n 是完全平方数.【证明】因方程1222-=-y x ① 有正整数解1==y x ，因此有无穷多组正整数解.任取一组解,,v u 则1222+=u v将上式两边同乘以2u ，得,)(2242u u uv +=故.1222+<<u uv u 所以2]2[u uv =是一个平方数，即取uv n =得出无穷多个符合要求的.n例9：设d c b a ,,,为正整数，.cd ab =证明：4444d c b a +++不是素数.【证明】由cd ab =,得出,,,,ut d vs c st b us a ====其中t s v u ,,,都是正整数. 因此))((44444444t s v u d c b a ++=+++不是素数. 例10：证明：不定方程1,,,1)1(>=-+z y x x x z y ①仅有一组正整数解2,2==y x 及.3=z【证明】首先，将①模1+x 化简，得),1(mod 1)1(1+≡-+x z 故z 是奇数.将①分解为.1)1(211+-+-=+---x x x x z z y易知x 必须是偶数，否则上式两边的奇偶性不同，类似地，将①变形为,1)1()1()1(121---=+++++++z y y x x x x 可见y 也是偶数.现在记,2,211y y x x ==则由①得 z y y x x x =++-+]1)1][(1)1[(11②因x 是偶数，故1)1(1-+y x 与1)1(1++y x 的最大公约数是2，又显然有1)1(|1-+y x x ，由这些及②推出，必须.21)1(,21)1(1111-=++=-+z y z y x x x这意味着,2211z z x >-故11=x ，即2=x ，所以2=y 及.3=z【评述】方程①是著名的卡特郎（Catalan ）猜想的特殊情形.卡特郎猜想32与23是仅有的一对差为1的正整数方幕,即不定方程1,,1>=-b a y x ba③只有一组正整数解2,2,3===a y x 及.3=b例11：证明：不定方程244z y x =+ ①没有正整数解.【证明】采用反证法，设①有正整数解，我们在所有这样的解中选 取一组使z 最小的解.论证的想法是由此构造出另一组解),,(t s r ，使得z t <<0，由于已选择为最小，这就导出矛盾.首先,此时必有1),(=y x ,因设),(y x d =而1>d ,则由①知24|z d ，即z d |2所以2,,(d z d y d x ）也是①的一组正整数解，但z dz<2，这和z 的选取相违. 将①改写为.)()(22222z y x =+由于1),(=y x ，故1),(22=y x 于是),,(222z y x 是一组本源的勾股数.由定理三知，存在整数b a b a b a ,,1),(,0=>>一奇一偶，使得（不妨设y 为偶数）.,2,222222b a z ab y b a x +=--= ②由222a b x =+及1),(=b a 知，a 是奇数，b 是偶数.再应用上述定理，存在整数q p q p q p ,,1),(,0=>>一奇一偶，使得 2222,2,q p a pq b q p x +==-=.由②得到),(4222q p pq y +=即),()2(222q p pq y +=因,1),(=q p 易知22,,q p q p +两两互素，上式表明它们的积是整数的平方，故存在正整数t s r ,,使得,,,22222t q p s q r p =+==从而.244t s r =+于是我们得出了①的一组正整数解).,,(t s r 但,4022z z a q p t <<=+<和z 的最小性矛盾.【评述1】由例10立即推出,费马方程,2,>=+n z y x nn n 当4=n 时没有正整数解.【评述2】例11的证明方法,称为无穷递推法,这是费马首先提出的一个重要方法.采用无穷递降法证明不定方程无正整数解（满足某种限制的解）的主要步骤是：从相反的结论出发，假设存在一组正整数解，设法造出这个方程的另一个正整数解，而新的解比原来的解“严格地小”.这里所谓严格的小，是指某一个与解有关的，取正整数的量严格递减.如上述过程可以无限地进行下去，则由于严格递减的正整数列只有有限多项，两者产生矛盾.有一些不定方程需要应用稍深入的同余知识：二次剩余（或称平方剩余）.这里只介绍一个最基本、最常用的结果：引理 设p 是34+k 型的素数，则)(mod 012p x ≡+ ③没有整数解.换句话说,对于素数1,2+x x 的素因子或者是2，或者)4(mod 1≡ 证明颇简单.假定有x 满足③，则 ),(mod 12p x -≡ 故).(mod )1(211p xp p ---≡但p x ，于是由费马小定理知，),(mod 11p x p ≡-进而),(mod 1)1(21p p =--即)(mod 11p ≡-，得2=p ，这不可能.例12：设p 是34+k 型的素数，n 是正整数且.|n p 若n 可以表示为两个素数的平方和，即存在整数,,y x 使得 22y x n +=① 则n 中p 的幂次是偶数.【证明】首先证明y x ,均被p 整除.假设不然，可设p x ，则有整数1x ，使).(mod 11p xx ≡以21x 乘①的两边，再模p ，得出（注意到n p |）).(mod 01)(21p y x ≡+因)4(mod 3≡p ，这与引理矛盾，故).,(||y x p 设),,(||y x p a 则.|2n p a 我们证明n p a ||，即n 中p 的幂次是偶数.记,,,112y p y x p x m p n ααα===则11,,y x m 都是整数，且p ).,(11y x 由①得.2121y x m +=假设m p |，则由上述相同的论证表明),(|11y x p ，导出矛盾，这就证明了本题的断言.【评述】例12的论证表明：如设p 是34+k 型的素数，若有整数y x ,使得)(m o d 022p y x ≡+ 则y x ,均被p 整除.例13：证明：方程532-=x y ①没有整数解.【证明】首先,若x 是偶数，将①模4得)4(mod 32≡y ，此不可能.若x 是奇数，当)4(mod 3≡x 时，由①得)4(m o d 22≡y ，仍不可能.故)4(mod 1≡x ，于是)4(m o d 312≡++x x ，仍不可能.故)4(mod 1≡x ，于是)4(mo d 312≡++x x ，因此12++x x 必有一个34+k 型的素因子p ，将①变形为4)1)(1(22-++-=x x x y ①并模p ，得)(mod 0222p y ≡+.由例12评述可知，必有),,2(|y p 即2=p ，这不可能.故方程①没有整数解.【评述1】上面的论证中，先用同余导出了（有解的）某些必要条件，目的是为了使①的右边产生34+k 型的素因子，以应用引理或例12评述中的事实.【评述2】任一个)4(mod 3≡的整数必有34+k 型的素因子.这一简单的结论在这一类论证中最为有用.。
