第17讲 不定方程中的辗转相除法
-
第
17
讲
不定方程中的辗转相除法
【链接方法
】
不定方程
(
组
)
是指未知数的个数多于方程的个数的方程
(
组
)
，
其特点是解往往有无穷多
个，不能惟一确定．
对于不定方程
(
组
)
，我们往往限定只求整数解，甚
至只求正整数解，加上条件限制后，
解就可确定．
二元一次不定方程是最简单的不定方程，
一些复杂的不定方程
(
组
)
常常转化为二元一次
不定方程问题加以解决，与之相关的性质有
：
设
a
、<
/p>
b
、
c
、
d
为整数，则不定方程
ax
< br>
by
c
有如下两个重要命题：
(1)
若
二元一次不定方程
ax+by=c
中，
a
和
b
的最大公约数不能整除
c
，
则方程没有整数
解
.
例如，方程
2x+4y=5
没有整数解
.
(2)
如果正整数
a,b
互质，则方程
ax+
by=1
有整数解，同时方程
ax+by=c
< br>有整数解
.
例如，
3x+5y
=7
，
3
与
5
互质，
x=-1,y=2
是这个方程的
一组整数解
.
（
3
< br>）如果
a,b
互质，且方程
ax
+by=c
有一组整数解
x
0
,y
0
(
称特解
)
，则此方程式的所有
整数解
(
称通解
)
可表示为
x
x
0
bt
x
x
0
bt
或
.
(
t
为整数）
(
t
为整数）
y
y
a
t
y
y
<
/p>
at
0
0
例如，
3x+5y=7
< br>的所有整数解可表示为
x<
/p>
1
5
t
.
(
t
为整数）
y
2
3
t
解不定方程
(
组
)
，
没有现成的模式、
固定的方法可循，
需要依据方程
(
组
)
的特点进行恰
当的变形，并灵活运用
以下知识与方法；观察法、奇数偶数，整数的整除性、分离整系数、
辗转相除法、因数分
解、配方利用非负数性质、穷举，乘法公式，不等式分析等．
辗转相除法
,
又名欧几里德算法（
Euclidean algorithm
）乃求两个正整数之最大公因
子的算法。
它是已知最古老的算法
,
其可追溯至公元前
300
年
.
它首次出现于欧几
里德的
《几
何原本》
（第
VII
卷，命题
i
和
ii
）中，而在中国则可以追溯至东汉出现的《九章算术》
.
它并不需要把二数作质因子分解
.
辗转相除法可以求出不定方程的一组整数解
.
【挑战例题】
一、观察法
【
例
1
】
求下列二元一次不定方程的一
切整数解：
1
< br>(1
）
2
x
3
y
5
(2)
5
x
10
y
< br>
20
二、分离整系数法
【
例
2
】
求方程
3
x
5
y
31
的整数解
.
< br>【
例
3
】
求方程
7
x
4
y
100
的所有正整数解
.
三、参数法
【
例
4
】
求
方程
7
x
1
9
y
213
的整数解
.
四、辗转相除法
【
< br>例
5
】求方程
42
x
29
y
5
的整数解
.
< br>【
例
6
】
求方程
19
x
180
y
1
的一组正整数解
.
2