论文部分内容阅读
【摘要】不定方程是數论中一个古老的分支，也是数论中一个重要的研究课题，它有着悠久的历史与丰富的内容.所谓不定方程是指解的范围为整数、正整数、有理数等的方程或方程组，其未知数的个数通常多于方程的个数.例如，2x y=5就是一个不定方程，它没有确定的解，它有无数多解.本文从各定理出发，详细探讨了定理的实质，并通过例题加以说明二元一次不定方程有无整数解及求出整数解的过程.
【关键词】不定方程;二元一次不定方程;找解;求解
引 言
所谓二元一次不定方程的一般形式是ax by=c，其中a，b，c是整数.当然，在求解时x，y也是整数，如果x，y不要求是整数，那么它的解一般都会有无穷多个，除非a和b其中有一个为零，且要求ab≠0，也就是a，b都不是0.注意：这个a，b里边如果有一个是0，那就不是不定方程了;如果a，b都是0，就要求c也是0，这个解就是所有的整数对，所以，研究a，b都不是0的情况.如果ab≠0，对二元一次不定方程解的研究就与研究线性方程组、常微分方程的解法非常类似，如线性方程组ax=b的通解就是ax=0的通解， ax=b的特解;要求常微分方程ay″ by′ cy=f（x）的解，也是先令f（x）=0，先求出通解，再加上等于f（x）的一个特解.遵照同样的方法，要找到二元一次不定方程所有的解，就是要找ax by=c的特解和ax by=0的通解.下面我们先来认识相关定理.
一、二元一次不定方程求解的相关定理
定理1[1]：设二元一次不定方程ax by=c ① （其中a，b，c是整数，且ab≠0）有一整数解x=x0，y=y0 ;设（a，b）=d，a=a1d，b=b1d，则①的一切解可以表示成
x=x0-b1t，y=y0 a1t. ②
其中t∈Z.
证明：先证②是①的解.由x=x0，y=y0是①式的解，有ax0 by0=c.将②式代入①式，得
a（x0-b1t） b（y0 a1t）=ax0-ab1t by0 ba1t，
又a=a1d，b=b1d，代入上式，得
a（x0-b1t） b（y0 a1t）=ax0-a1db1t by0 b1da1t=ax0 by0=c.
所以②是①的解.
下面证①的解为②的形式.由ax by=c，ax0 by0=c，两式相减，得a（x-x0） b（y-y0）=0，把a=a1d，b=b1d代入，a1d（x-x0） b1d（y-y0）=0a1（x-x0）=-b1（y-y0）， ③所以a1|b1（y-y0），因为a1，b1互质，所以a1|y-y0y-y0=a1ty=y0 a1t代入③式，a1（x-x0）=-b1a1t，因为ab≠0，所以a1，b1≠0，有x-x0=-b1tx=x0-b1t，所以①的解为②的形式.
这个解的过程，首先要找到ax by=0的通解，设（a，b）=d，a=a1d，b=b1d，写成a1dx b1dy=0，约去最大公因数d，a1x=-b1ya1|b1y，因为（a1，b1）=1，所以a1|yy=a1t，代回a1x=-b1ya1x=-b1a1tx=-b1t;然后找到ax by=c的一个特解.ax by=0的通解的形式已经给出来了：x=-b1t，y=a1t，剩下只需找x0，y0这个特解，所以目的就是找ax by=c的特解，如果能从方程中直接看出这个特解来，那么ax by=c的通解就很容易写出来，如方程6x-9y=-3，容易看出它的一个特解x0=1，y0=1.因为（6，9）=3，a=6=a1d=2×3，b=9=b1d=3×3，通解是x=x0-b1t=1-3t，y=y0 a1t=1 2t.但是，不是所有的ax by=c都能且容易看出特解，怎样才能找到它的特解？这个特解到底存不存在呢？肯定的是这个特解有时候是不一定存在的.比如，方程2x 8y=1，它的特解明显是不存在的，因为2x和8y都是偶数，加起来也是偶数，而方程右边是奇数，偶数等于奇数是不可能的，所以这个方程的特解不存在.于是，关键是讨论对于①这种形式的方程什么时候有解，有解的话怎么求？
定理2[1]：①式有整数解，当且仅当（a，b）|c.
证明：“充分性”已知①式有整数解x=x0，y=y0，有ax0 by0=c，设d=（a，b），则d|a，d|b，于是d|ax0 by0，即d|c.
“必要性”仍设d=（a，b），a=a1d，b=b1d，由d|cc=c1d，则ax by=ca1dx b1dy=c1da1x b1y=c1.
由（a1，b1）=1，存在整数s，t，使得a1s b1t=1a1sc1 b1tc1=c1，a1x b1y=c1有解，x=sc1，y=tc1，也是①的解.
这个定理给了一个①式有整数解的充要条件，可是知道它有解，这个解怎么找到呢？实际上定理2的证明过程给出了一个找解的办法.先找出a1s b1t=1的解x=s，y=t，给式子两边乘上c1，a1sc1 b1tc1=c1的解为x=sc1，y=tc1.因为a1x b1y=c1与ax by=c等价，所以它们同解.所以问题的焦点就归结为求a1s b1t=1的解x，y，前提是（a1，b1）=1，x，y都乘上c1，ax by=c的解就出来了.
定理3[2]：若a，b是任意两个正整数，则
Qka-Pkb=（-1）k-1rk，k=1，2，…，n. 其中P0=1，P1=q1，Pk=qkPk-1 Pk-2，Q0=0，Q1=1，Qk=qkQk-1 Qk-2，其中k=1，2，…，n.
现取a1，b1，取k=n，知d=rn，
Qna1-Pnb1=（-1）n-1d，两边同乘（-1）n-1，（-1）n-1Qna1-（-1）n-1Pnb1=d（-1）n-1Qna1 （-1）nPnb1=d，取s=（-1）n-1Qn，t=（-1）nPn，则a1s b1t=d=1.可以利用这个办法来找s和t，这里边要找到s和t，需要把Qn，Pn，n算出来.由定理3知，Qn，Pn有相同的递推关系，根据递推关系，所有的Q，P都能够求出来，而且这个qk是带余除法里的不完全商，所以带余除法也得把它写出来.首先q0是没有的，是从q1开始，可以根据带余除法把所有的q给找到.当n不是太大，计算不是特别困难.最后用x=（-1）n-1Qn，y=（-1）nPn这个表达式就可以把这个解给找出来了.
二、例 析
例1 求25x 15y=100的一切整数解.
解 ∵25，15=5，5|100，故方程有解.把方程变形为5x 3y=20，先求5x 3y=1的解，此处a=5，b=3，（a，b）=1，用辗转相除法：5=3×1 2，3=2×1 1，
故n=2，q1=1，q2=1，列表如下：
因此，5x 3y=1的一个解是x=（-1）2-1Q2=-2，y=（-1）2P2=2，5x 3y=20的一個解为x=-2×20=-40，y=2×20=40.由定理1知，原方程的一切解可以表示成x=-40-3t，y=40 5t，t∈Z.
例2 求不定方程4x 6y=86的解.
解 ∵（4，6）=2，2|86，故方程有解.把方程变形为2x 3y=43，先求2x 3y=1的解，用辗转相除法要求a
【关键词】不定方程;二元一次不定方程;找解;求解
引 言
所谓二元一次不定方程的一般形式是ax by=c，其中a，b，c是整数.当然，在求解时x，y也是整数，如果x，y不要求是整数，那么它的解一般都会有无穷多个，除非a和b其中有一个为零，且要求ab≠0，也就是a，b都不是0.注意：这个a，b里边如果有一个是0，那就不是不定方程了;如果a，b都是0，就要求c也是0，这个解就是所有的整数对，所以，研究a，b都不是0的情况.如果ab≠0，对二元一次不定方程解的研究就与研究线性方程组、常微分方程的解法非常类似，如线性方程组ax=b的通解就是ax=0的通解， ax=b的特解;要求常微分方程ay″ by′ cy=f（x）的解，也是先令f（x）=0，先求出通解，再加上等于f（x）的一个特解.遵照同样的方法，要找到二元一次不定方程所有的解，就是要找ax by=c的特解和ax by=0的通解.下面我们先来认识相关定理.
一、二元一次不定方程求解的相关定理
定理1[1]：设二元一次不定方程ax by=c ① （其中a，b，c是整数，且ab≠0）有一整数解x=x0，y=y0 ;设（a，b）=d，a=a1d，b=b1d，则①的一切解可以表示成
x=x0-b1t，y=y0 a1t. ②
其中t∈Z.
证明：先证②是①的解.由x=x0，y=y0是①式的解，有ax0 by0=c.将②式代入①式，得
a（x0-b1t） b（y0 a1t）=ax0-ab1t by0 ba1t，
又a=a1d，b=b1d，代入上式，得
a（x0-b1t） b（y0 a1t）=ax0-a1db1t by0 b1da1t=ax0 by0=c.
所以②是①的解.
下面证①的解为②的形式.由ax by=c，ax0 by0=c，两式相减，得a（x-x0） b（y-y0）=0，把a=a1d，b=b1d代入，a1d（x-x0） b1d（y-y0）=0a1（x-x0）=-b1（y-y0）， ③所以a1|b1（y-y0），因为a1，b1互质，所以a1|y-y0y-y0=a1ty=y0 a1t代入③式，a1（x-x0）=-b1a1t，因为ab≠0，所以a1，b1≠0，有x-x0=-b1tx=x0-b1t，所以①的解为②的形式.
这个解的过程，首先要找到ax by=0的通解，设（a，b）=d，a=a1d，b=b1d，写成a1dx b1dy=0，约去最大公因数d，a1x=-b1ya1|b1y，因为（a1，b1）=1，所以a1|yy=a1t，代回a1x=-b1ya1x=-b1a1tx=-b1t;然后找到ax by=c的一个特解.ax by=0的通解的形式已经给出来了：x=-b1t，y=a1t，剩下只需找x0，y0这个特解，所以目的就是找ax by=c的特解，如果能从方程中直接看出这个特解来，那么ax by=c的通解就很容易写出来，如方程6x-9y=-3，容易看出它的一个特解x0=1，y0=1.因为（6，9）=3，a=6=a1d=2×3，b=9=b1d=3×3，通解是x=x0-b1t=1-3t，y=y0 a1t=1 2t.但是，不是所有的ax by=c都能且容易看出特解，怎样才能找到它的特解？这个特解到底存不存在呢？肯定的是这个特解有时候是不一定存在的.比如，方程2x 8y=1，它的特解明显是不存在的，因为2x和8y都是偶数，加起来也是偶数，而方程右边是奇数，偶数等于奇数是不可能的，所以这个方程的特解不存在.于是，关键是讨论对于①这种形式的方程什么时候有解，有解的话怎么求？
定理2[1]：①式有整数解，当且仅当（a，b）|c.
证明：“充分性”已知①式有整数解x=x0，y=y0，有ax0 by0=c，设d=（a，b），则d|a，d|b，于是d|ax0 by0，即d|c.
“必要性”仍设d=（a，b），a=a1d，b=b1d，由d|cc=c1d，则ax by=ca1dx b1dy=c1da1x b1y=c1.
由（a1，b1）=1，存在整数s，t，使得a1s b1t=1a1sc1 b1tc1=c1，a1x b1y=c1有解，x=sc1，y=tc1，也是①的解.
这个定理给了一个①式有整数解的充要条件，可是知道它有解，这个解怎么找到呢？实际上定理2的证明过程给出了一个找解的办法.先找出a1s b1t=1的解x=s，y=t，给式子两边乘上c1，a1sc1 b1tc1=c1的解为x=sc1，y=tc1.因为a1x b1y=c1与ax by=c等价，所以它们同解.所以问题的焦点就归结为求a1s b1t=1的解x，y，前提是（a1，b1）=1，x，y都乘上c1，ax by=c的解就出来了.
定理3[2]：若a，b是任意两个正整数，则
Qka-Pkb=（-1）k-1rk，k=1，2，…，n. 其中P0=1，P1=q1，Pk=qkPk-1 Pk-2，Q0=0，Q1=1，Qk=qkQk-1 Qk-2，其中k=1，2，…，n.
现取a1，b1，取k=n，知d=rn，
Qna1-Pnb1=（-1）n-1d，两边同乘（-1）n-1，（-1）n-1Qna1-（-1）n-1Pnb1=d（-1）n-1Qna1 （-1）nPnb1=d，取s=（-1）n-1Qn，t=（-1）nPn，则a1s b1t=d=1.可以利用这个办法来找s和t，这里边要找到s和t，需要把Qn，Pn，n算出来.由定理3知，Qn，Pn有相同的递推关系，根据递推关系，所有的Q，P都能够求出来，而且这个qk是带余除法里的不完全商，所以带余除法也得把它写出来.首先q0是没有的，是从q1开始，可以根据带余除法把所有的q给找到.当n不是太大，计算不是特别困难.最后用x=（-1）n-1Qn，y=（-1）nPn这个表达式就可以把这个解给找出来了.
二、例 析
例1 求25x 15y=100的一切整数解.
解 ∵25，15=5，5|100，故方程有解.把方程变形为5x 3y=20，先求5x 3y=1的解，此处a=5，b=3，（a，b）=1，用辗转相除法：5=3×1 2，3=2×1 1，
故n=2，q1=1，q2=1，列表如下：
因此，5x 3y=1的一个解是x=（-1）2-1Q2=-2，y=（-1）2P2=2，5x 3y=20的一個解为x=-2×20=-40，y=2×20=40.由定理1知，原方程的一切解可以表示成x=-40-3t，y=40 5t，t∈Z.
例2 求不定方程4x 6y=86的解.
解 ∵（4，6）=2，2|86，故方程有解.把方程变形为2x 3y=43，先求2x 3y=1的解，用辗转相除法要求a