第17讲 不定方程中的辗转相除法
【链接方法】
不定方程(组) 是指未知数的个数多于方程的个数的方程(组) ，其特点是解往往有无穷多个，不能惟一确定．
对于不定方程(组) ，我们往往限定只求整数解，甚至只求正整数解，加上条件限制后，解就可确定．
二元一次不定方程是最简单的不定方程，一些复杂的不定方程(组) 常常转化为二元一次不定方程问题加以解决，与之相关的性质有：
设a 、b 、c 、d 为整数，则不定方程ax +by =c 有如下两个重要命题：
(1)若二元一次不定方程ax+by=c中，a 和b 的最大公约数不能整除c ，则方程没有整数解. 例如，方程2x+4y=5没有整数解.
(2)如果正整数a,b 互质，则方程ax+by=1有整数解，同时方程ax+by=c有整数解. 例如，3x+5y=7，3与5互质，x=-1,y=2是这个方程的一组整数解.
（3）如果a,b 互质，且方程ax+by=c有一组整数解x 0,y 0(称特解) ，则此方程式的所有整数解(称通解) 可表示为
⎧x =x 0+bt ⎧x =x 0-bt 或 . (t 为整数）(t 为整数）⎨⎨y =y -at y =y +at 00⎩⎩
例如，3x+5y=7的所有整数解可表示为⎨⎧x =-1-5t . (t 为整数）⎩y =2+3t
解不定方程(组) ，没有现成的模式、固定的方法可循，需要依据方程(组) 的特点进行恰当的变形，并灵活运用以下知识与方法；观察法、奇数偶数，整数的整除性、分离整系数、辗转相除法、因数分解、配方利用非负数性质、穷举，乘法公式，不等式分析等．
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至公元前300年. 它首次出现于欧几里德的《几何原本》（第VII 卷，命题i 和ii ）中，而在中国则可以追溯至东汉出现的《九章算术》. 它并不需要把二数作质因子分解. 辗转相除法可以求出不定方程的一组整数解.
【挑战例题】
一、观察法
【例1】求下列二元一次不定方程的一切整数解：
(1）2x +3y =5 (2) 5x +10y =20
二、分离整系数法
【例2】求方程3x +5y =31的整数解.
【例3】求方程7x +4y =100的所有正整数解.
三、参数法
【例4】求方程7x +19y =213的整数解.
四、辗转相除法
【例5】求方程42x -29y =5的整数解.
【例6】求方程19x -180y =1的一组正整数解.
【提升能力】
1. 下列不定方程没有整数解的是（ ）
A 、3x+2y=12 B、2x-11y=3 C、3x+6y=8 D、99x+98y=1
2.(河南省竞赛题) 如图，在高速公路上从3千米处开始，每隔4千米设一个速度限制标志，而且从10千米处开始，每隔9千米设一个测速照相标志，则刚好在19千米处同时设置这两种标志．问下一个同时设置这两种标志的地点的千米数是( )．
A．32千米 B．37千米 C．55千米 D．90千米
3. 三元一次方程x+y+z=1999的非负整数解的个数有（ ）
A ．20001999个 B．19992000个 C．2001000个 D．2001999个
4. 正整数m 、n 满足8m+9n=mn+6，则m 的最大值为 ．
5．1998年某人的年龄恰等于他出生的公元年数的数字之和，那么他的年龄是 岁．
6. 求方程3x+5y=1的整数解. （试试观察法）
7. (莫斯科数学奥林匹克试题) 求方程15x+52y=6的所有整数解．（试试参数法）
8. 求方程7x +19y =213的所有正整数解．（试试分离系数法）
9. 求方程37x +107y =25的整数解．（试试辗转相除法）
10. 某国硬币有5分和7分两种，问用这两种硬币支付142分货款，有多少种不同的方法？
11. 求方程9x +24y －5z =1000的整数解．
12. (上海市”金桥杯”数学知识应用竞赛试题) 某布店的一页账簿上沾了墨水，如下表所示：
所卖呢料米数看不清楚了，但记得是卖了整数米；金额项目只看到后面3个数码7.28，但前面的3个数码看不清楚了，请你帮助查清这笔账．
第17讲 不定方程中的辗转相除法
【链接方法】
不定方程(组) 是指未知数的个数多于方程的个数的方程(组) ，其特点是解往往有无穷多个，不能惟一确定．
对于不定方程(组) ，我们往往限定只求整数解，甚至只求正整数解，加上条件限制后，解就可确定．
二元一次不定方程是最简单的不定方程，一些复杂的不定方程(组) 常常转化为二元一次不定方程问题加以解决，与之相关的性质有：
设a 、b 、c 、d 为整数，则不定方程ax +by =c 有如下两个重要命题：
(1)若二元一次不定方程ax+by=c中，a 和b 的最大公约数不能整除c ，则方程没有整数解. 例如，方程2x+4y=5没有整数解.
(2)如果正整数a,b 互质，则方程ax+by=1有整数解，同时方程ax+by=c有整数解. 例如，3x+5y=7，3与5互质，x=-1,y=2是这个方程的一组整数解.
（3）如果a,b 互质，且方程ax+by=c有一组整数解x 0,y 0(称特解) ，则此方程式的所有整数解(称通解) 可表示为
⎧x =x 0+bt ⎧x =x 0-bt 或 . (t 为整数）(t 为整数）⎨⎨y =y -at y =y +at 00⎩⎩
例如，3x+5y=7的所有整数解可表示为⎨⎧x =-1-5t . (t 为整数）⎩y =2+3t
解不定方程(组) ，没有现成的模式、固定的方法可循，需要依据方程(组) 的特点进行恰当的变形，并灵活运用以下知识与方法；观察法、奇数偶数，整数的整除性、分离整系数、辗转相除法、因数分解、配方利用非负数性质、穷举，乘法公式，不等式分析等．
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至公元前300年. 它首次出现于欧几里德的《几何原本》（第VII 卷，命题i 和ii ）中，而在中国则可以追溯至东汉出现的《九章算术》. 它并不需要把二数作质因子分解. 辗转相除法可以求出不定方程的一组整数解.
【挑战例题】
一、观察法
【例1】求下列二元一次不定方程的一切整数解：
(1）2x +3y =5 (2) 5x +10y =20
二、分离整系数法
【例2】求方程3x +5y =31的整数解.
【例3】求方程7x +4y =100的所有正整数解.
三、参数法
【例4】求方程7x +19y =213的整数解.
四、辗转相除法
【例5】求方程42x -29y =5的整数解.
【例6】求方程19x -180y =1的一组正整数解.
【提升能力】
1. 下列不定方程没有整数解的是（ ）
A 、3x+2y=12 B、2x-11y=3 C、3x+6y=8 D、99x+98y=1
2.(河南省竞赛题) 如图，在高速公路上从3千米处开始，每隔4千米设一个速度限制标志，而且从10千米处开始，每隔9千米设一个测速照相标志，则刚好在19千米处同时设置这两种标志．问下一个同时设置这两种标志的地点的千米数是( )．
A．32千米 B．37千米 C．55千米 D．90千米
3. 三元一次方程x+y+z=1999的非负整数解的个数有（ ）
A ．20001999个 B．19992000个 C．2001000个 D．2001999个
4. 正整数m 、n 满足8m+9n=mn+6，则m 的最大值为 ．
5．1998年某人的年龄恰等于他出生的公元年数的数字之和，那么他的年龄是 岁．
6. 求方程3x+5y=1的整数解. （试试观察法）
7. (莫斯科数学奥林匹克试题) 求方程15x+52y=6的所有整数解．（试试参数法）
8. 求方程7x +19y =213的所有正整数解．（试试分离系数法）
9. 求方程37x +107y =25的整数解．（试试辗转相除法）
10. 某国硬币有5分和7分两种，问用这两种硬币支付142分货款，有多少种不同的方法？
11. 求方程9x +24y －5z =1000的整数解．
12. (上海市”金桥杯”数学知识应用竞赛试题) 某布店的一页账簿上沾了墨水，如下表所示：
所卖呢料米数看不清楚了，但记得是卖了整数米；金额项目只看到后面3个数码7.28，但前面的3个数码看不清楚了，请你帮助查清这笔账．