辗转定理及其应用.doc

辗转定理及其在不定方程求解中的应用一，辗转数表与辗转定理从经典的辗转相除法出发，反转相乘，可构成辗转相除及其反转相乘的数据表，简称辗转数表。定义 设互质正整数对(r0,r1), r0r1。三个整数序列rn, qn, kn如下表所示：（r,q,k之后的数字，字母与括号均为下标）r0r1r2r(n-1)rnr(n+1)=1q1q2q(n-1)qnk0k1k2k(n-1)kn=1k(n+1)=0同时满足以下递归关系式：r(i-1)=qi*ri+r(i+1)。i=1, ,n。.(1) (即，r(i-1)/ri=qir(i+1)，商qi，余数r(i+1)。) k(i-1)=qi*ki+k(i+1)，i=n, ,1。.(2)那么称此表为数对（r0,r1）的辗转数表，称n为辗转阶数，称数对（k0,k1）为数对（ r0,r1）的辗转数对。注意：从数对（r0,r1）出发，用除法计算qi及r(i+1)是从左向右，即i从1到n；而从kn=1, k(n+1)=0开始，用乘法与加法计算ki是从右向左，即i从n到1。最终得到数对（k0,k1）。例如r0=2310, r1=13，其转除数表为231013941177125333210其辗转阶数n=3；而数对（2310, 13）的辗转数对是（533, 3）。由辗转数表，可引出辗转定理。辗转定理 设互质正整数对（r0,r1）的n阶辗转数对（k0,k1）。那么，r0*k1-r1*k0=(-1)n+1.(3)证明：用归纳法证明。n=1时，辗转数表为r0r11q1k0=q1k1=10此时，r0=q1*r1+1，即r0*k0-r1*k1=1。 设对于n-1阶，式（3）成立。那么，n阶的辗转数表r0r1r2r(n-1)rnr(n+1)=1q1q2q(n-1)qnk0k1k2k(n-1)kn=1k(n+1)=0的子表r1r2r(n-1)rnr(n+1)=1q2q(n-1)qnk1k2k(n-1)kn=1k(n+1)=0是一个n-1阶的辗转数表。因此，有r1*k2-r2*k1=(-1)n而 r0*k1-r1*k0=r0*k1-r1*k0 =(q1*r1+r2)*k1-r1*(q1*k1+k2) =r2*k1-r1*k2 =-(-1)n =(-1)n+1 证毕由式(3)可知推论 互质正整数对（r0,r1）的n阶辗转数对（k0,k1）也是互质的。二，辗转数表在求解不定方程中的应用由二元一次不定方程ax+by=c解的定理知道，方程有整数解的充要条件是a,b的最大公约数(a,b)能整除c。而且如果(x0,y0)是方程的一个特解，则方程的通解是x=x0-bt, y=y0+at (t为整参数，下同)(4)因此，二元一次不定方程的求解仅需限定在a,b互质，c=1时求其特解即可。虽然已有多种方法求特解，但利用辗转数表及辗转定理更为方便。以下约定a,b为互质正整数，ab。令r0=a, r1=b。数对a,b的n阶辗转数对为k0,k1。由辗转定理可求二元一次不定方程的特解。为清晰明确起见，下面就分别四种情况加以讨论。1， 二元一次不定方程ax-by=1，由辗转定理其特解为当n为奇数时，x0=k1, y0=k0；当n为偶数时，x0=-k1, y0=-k0，同余于x0=b-k1, y0=a-k0。方程的通解是x=x0+bt, y=y0+at。由变元代换，-y代换y，或 -x代换x，可得2， 二元一次不定方程ax+by=1，其特解为当n为奇数时，x0=k1, y0=-k0；当n为偶数时，x0=-k1, y0=k0。方程的通解是x=x0+bt, y=y0-at。3， 二元一次不定方程 -ax+by=1，其特解为当n为奇数时，x0=-k1, y0=-k0；当n为偶数时，x0=k1, y0=k0。方程的通解是x=x0-bt, y=y0-at。4， 二元一次不定方程 -ax-by=1，其特解为当n为奇数时，x0=-k1, y0=k0；当n为偶数时，x0=k1, y0=-k0。方程的通解是x=x0-bt, y=y0+at。例1，不定方程30x-7y=1。互质正整数数对(a=30, b=7)的辗转数表为307214313319其辗转阶数n= 2。所以，x0=-3, y0=-13，同余于x0=4，y0=17。方程的通解是x=4+7t, y=17+13t。例2，不定方程30x+7y=1。同上，n=2, 特解x0=-3, y0=13；通解是x=-3+7t y=13-13t。例3，不定方程2310x+13y=1。由上节，n=3, k0=533, k1=3。特解x0=3, y0=-533；通解是x=3+13t y=-533-2310t。例4，不定方程 -2310x-13y=1。同上，n=3, k0=533, k1=3。特解x0=-3, y0=533；