輾轉(zhuǎn)相除法求解二元一次不定方程

王曉英

（赤峰學(xué)院，內(nèi)蒙古 赤峰 024000）

輾轉(zhuǎn)相除法求解二元一次不定方程

王曉英

（赤峰學(xué)院，內(nèi)蒙古 赤峰 024000）

本文旨在用輾轉(zhuǎn)相除法求出二元一次不定方程的一個整數(shù)解，進而寫出其一切整數(shù)解.

二元一次不定方程；整數(shù)解；輾轉(zhuǎn)相除法

1 引言

二元一次不定方程的一般形式是

其中a,b,c是整數(shù)，a,b都不是0.首先討論二元一次不定方程有整數(shù)解的條件.

定理1[1]（1）式有整數(shù)解的充分必要條件是(a,b)|c.

證明 若（1）式有整數(shù)解，設(shè)為x0,y0，則ax0+by0=c，因為(a,b)|a,(a,b)|b，所以(a,b)|ax0+by0，即(a, b)|c.

反之，若(a,b)|c，則存在整數(shù)c1，使c=c1(a,b).又因為一定存在整數(shù)s,t，使as+bt=(a,b)，所以有asc1+btc1=(a,b)c1=c.令x0=c1s,y0=c1t，即得ax0+by0=c，故（1）式有整數(shù)解x0,y0.

定理2[1]設(shè)（1）式有一整數(shù)解x0,y0；又設(shè)(a,b) =d，a=a1d,b=b1d，則（1）的一切解可以表示成

其中t=0,±1,±2,…….

由定理2可知，（1）式若有整數(shù)解，只需求出（1）式的一個特殊解即可寫出一切解.

2 輾轉(zhuǎn)相除法

定理3[1]（帶余數(shù)除法） 若a,b是兩個整數(shù)，其中b>0，則存在著兩個整數(shù)q及r，使得

成立，而且q及r是唯一的.

設(shè)a>0,b>0，由帶余數(shù)除法可以得到：

上述計算方法叫作輾轉(zhuǎn)相除法.其中rn=(a,b)，并且不難得出輾轉(zhuǎn)相除法中任一余數(shù)ri(i=1,2,…,n)與a,b的關(guān)系為：

其中P0=1,P1=q1,Pk=qkPk-1+Pk-2,

Q0=0,Q1=1,Qk=qkQk-1+Qk-2,k=2,3,…,n.

3 二元一次不定方程的解法

由定理1的證明看到，（1）式在有解的情況下，是先證明ax+by=(a,b)有解.因此要找出求出一個特殊解的方法，應(yīng)該從這個方程著手，而這個方程的解與的解完全相同，并且.所以只需求出形如的一個特殊解.

由輾轉(zhuǎn)相除法我們能求出|a|x+|b|y=1的一個特殊解，由此又很容易得出（3）式的一個解.因此，我們不妨假定（3）式中a>0,b>0.由（2）式可得出a[ (-1)n-1Qn]+b[(-1)nPn]=1，因此（3）式有一特殊解：x= (-1)n-1Qn,y=(-1)nPn.根據(jù)（2）式可以由下表更直觀地給出求解Pn,Qn的過程：

由（3）式很容易得出ax+by=c的一個特殊解：

例1求107x+37y=25的一切整數(shù)解.

解(107,37)=1,1|25，故不定方程有解.

列下表求P3，Q3：

故107x+37y=1的特殊解是

107 x+37y=25的特殊解是

故107x+37y=25的一切整數(shù)解為：

或x=3-37t,y=-8+107t(t=0,±1,±2,……).

例2求111x-321y=75的一切整數(shù)解.

解(111,321)=3,3|75，故不定方程有解，且原方程的解與37x-107y=25的解完全相同.先解107x+37y=1，如例1，得出107x+37y=1的一個解：

易得37x-107y=1的一個解：

故37x-107y=25的一切解可表成：

或x=-8+107t,y=-3+37t(t=0,±1,±2,……).

〔1〕閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].北京：高等教育出版社，1998.

〔2〕胡學(xué)松，張勇宏，龔五星.二元一次不定方程整數(shù)解的通解公式[J].數(shù)學(xué)通訊，1995（6）.

〔3〕朱志嘉，周定遠(yuǎn).大系數(shù)二元一次不定方程解法探討[J].數(shù)學(xué)通訊，1996（2）.

O122.2

A

1673-260X（2014）12-0006-02