证若(1)式有一整数解，设为，则 axo by c. 但(a,b)整除a及b,因而整除c,故条件的必要性获证 反之，若(a,b)川c,则c=a(a,b),G是整数.由第一章§3 推论1.1，存在两个整数s,1满足下列等式 as bt=(a,b). 令=sG,%=G,即得ax+b%=C,故(1)式有整数解，% 证完 对于二元一次不定方程，我们还没有给出求(1)式的一个整数 解的方法，下面应用辗转相除法解决这个问题 由定理2的证明看到，在有解的情况下，是先证明方程 ax by (a,b) 有解因此我们要找出一个求特殊解的方法，应该从这个方程着 手首先上述方程的解与方程 b (a,b)x+(a.b)y=1 的解完全相同，而在这个方程里，未知数x,y的系数是互质的，所 以只要讨论如何求出形式如 ax+by=1,(a,b)=1 (3) 的方程的一个整数解就够了容易看出，由(3)的一个特殊解，可以 得出方程引a|x+|b1y=1的一个特殊解，反之亦然因此为简单 起见，可以假定a>0,b>0应用辗转相除法，可以得到： a=bg +r,0<n<b, b=ng+n,0<n<n, . In-2 Ia-I qn a,0<In Fa.1, 因为(a,b)=1,故rn=1,由第一章§3定理1， ·26·
证 若(1 )式有一整数解, 设为 x0 , y0 ,则 ax0 + by0 = c . 但( a, b) 整除 a 及 b, 因而整除 c,故条件的必要性获证 . 反之,若( a, b) | c, 则 c = c1 ( a, b) , c1 是整数 .由第一章§3 推论 1.1,存在两个整数 s, t 满足下列等式 as + bt = ( a, b) . 令 x0 = sc1 , y0 = tc1 ,即得 ax0 + by0 = c, 故( 1)式有整数解 x0 , y0 . 证完 对于二元一次不定方程,我们还没有给出求( 1) 式的一个整数 解的方法,下面应用辗转相除法解决这个问题 . 由定理 2 的证明看到,在有解的情况下, 是先证明方程 ax + by = ( a, b) 有解 .因此我们要找出一个求特殊解的方法, 应该从这个方程着 手 .首先上述方程的解与方程 a ( a, b) x + b ( a, b) y = 1 的解完全相同,而在这个方程里, 未知数 x , y 的系数是互质的, 所 以只要讨论如何求出形式如 ax + by = 1 , ( a, b) = 1 ( 3) 的方程的一个整数解就够了 .容易看出, 由(3 )的一个特殊解, 可以 得出方程 | a | x + | b | y = 1 的一个特殊解, 反之亦然 .因此为简单 起见,可以假定 a > 0, b > 0 .应用辗转相除法, 可以得到: a = bq1 + r1 ,0 < r1 < b, b = r1 q2 + r2 , 0 < r2 < r1 , . rn - 2 = rn - 1 qn + rn , 0 < rn < rn - 1 , rn - 1 = rn qn + 1 . 因为( a, b) = 1, 故 rn = 1 ,由第一章§3 定理 1 , · 26 ·
Q.a-P.b=(-1)-n 于是 a[(-1)-Qn]+b[(-1)"Pn]=1. 因此(3)式有一个特殊解： x=（-1)Qm,y=(-1)"Pm (4) 又由第一章§3定理1 R=1,R=9,R=gP+月k=2,.,n.(5) Q=0,Q=1,Q4=4Q.1+Q.2, 由(5)可以得出求(4)式（即(3）式的一个特殊解)的方法，即先由辗 转相除法求出，9，.，g,把它们写在下表的第二横行里面： 其次在第二及第三直行写下R=1,Q。=0,P=,Q=1,然后 利用公式(5)，顺次求出P,Q,P,Q,.,P,Q(表中+号和连 接到P1,Q的直线可以帮助我们记忆)，最后即得(4). 例1求7x+4y=100的一切整数解. 解先解7x+4y=1,此处a=7,b=4,(a,b)=1 因此7x+4y=1的一个解是x=(-1)1=-1,y=(-1)2=2 故原方程的一个解是 x=-100,y=200 ·27·
Qn a - Pn b = ( - 1) n - 1 rn . 于是 a[ ( - 1) n - 1 Qn ] + b[ ( - 1 ) n Pn ] = 1 . 因此(3 )式有一个特殊解: x = ( - 1 ) n - 1 Qn , y = ( - 1) n Pn . ( 4) 又由第一章§3 定理 1 P0 = 1, P1 = q1 , Pk = qkPk - 1 + Pk - 2 , Q0 = 0 , Q1 = 1, Qk = qk Qk - 1 + Qk - 2 , k = 2, ., n . ( 5) 由(5 )可以得出求( 4) 式(即( 3) 式的一个特殊解)的方法, 即先由辗 转相除法求出 q1 , q2 ,., qn , 把它们写在下表的第二横行里面: 其次在第二及第三直行写下 P0 = 1, Q0 = 0 , P1 = q1 , Q1 = 1, 然后 利用公式(5 ) , 顺次求出 P2 , Q2 , P3 , Q3 ,., Pn , Qn (表中 + 号和连 接 qk 到 Pk - 1 , Qk - 1的直线可以帮助我们记忆 ) ,最后即得 (4 ) . 例 1 求 7 x + 4 y = 100 的一切整数解 . 解 先解 7 x + 4 y = 1, 此处 a = 7, b = 4, ( a, b) = 1 . 因此7 x + 4 y = 1 的一个解是 x = ( - 1) b 2 - 1 1 = - 1, y = ( - 1) 2 2 = 2 . 故原方程的一个解是 x = - 100, y = 200 . · 27 ·
由定理1其一切解可以表成 x=-41-100,y=7t+200(t=0,±1，±2，.) 在本章开始所提出的张丘建的原题中，x及y代表鸡翁，鸡母的个 数，所以必须使得x≥0，y≥0因此 .200≤1≤-25 7 故1=-28，-27，-26，-25又鸡雏数是z=100-x-y=-31 这样就得到下面四组解答： x=12x=8x=4x=0 y=4,y=11,y=18,y=25 2=842=812=782=75 例2求111x-321y=75的一切整数解. 解(111，·321)=3，而3|75，故有解，且原方程的解与 37x-107y=25的解完全相同今先解107x+37y=1. 故107x+37y=1的一解是x=(-1)9=9,y=(-1)26=-26 37x-107y=1的一解是x=-26,y=-9故37x-107y=25的 一切解可以表成 x=-26×25+107t,y=-9×25+371(t=0,±1，±2，.)， 或 x=-8+1071,y=-3+371(t=0,±1，±2，.). 在结束本节之前，我们来研究一下以往中学教科书中二元 ·28·
由定理 1 其一切解可以表成 x = - 4 t - 100 , y = 7 t + 200 ( t = 0 , ± 1, ± 2, .) . 在本章开始所提出的张丘建的原题中, x 及 y 代表鸡翁, 鸡母的个 数,所以必须使得 x≥0, y≥0 .因此 - 200 7 ≤ t ≤ - 25 . 故 t = - 28, - 27 , - 26, - 25 .又鸡雏数是 z = 100 - x - y = - 3 t . 这样就得到下面四组解答: x = 12 y = 4 z = 84 , x = 8 y = 11 z = 81 , x = 4 y = 18 z = 78 , x = 0 y = 25 z = 75 . 例 2 求 111 x - 321 y = 75 的一切整数解 . 解 ( 111, - 321 ) = 3, 而 3 | 75, 故 有解, 且 原方程 的解 与 37 x - 107 y = 25的解完全相同 .今先解 107 x + 37 y = 1 . 故 107 x + 37 y = 1 的一解是 x = ( - 1 ) 2 9 = 9, y = ( - 1) 3 26 = - 26 . 37 x - 107 y = 1 的一解是 x = - 26, y = - 9 .故 37 x - 107 y = 25 的 一切解可以表成 x = - 26 × 25 + 107 t , y = - 9 × 25 + 37 t ( t = 0, ± 1, ± 2 ,.) , 或 x = - 8 + 107 t , y = - 3 + 37 t ( t = 0 , ± 1, ± 2, .) . 在结束本节之前,我们来研究一下以往中学教科书中二元一 · 28 ·
次不定方程解法的理论根据， 设给定一个适合下列条件的二元一次不定方程 ax+y=c,a>b>0,(a,b)=1 (6) 那么由第一章§1定理4，知道有整数，q1,n,满足条件a= bg+n,0≤n<b,c=bg+H,0≤H<b又由第一章§2定理3 得到(b,n)=（a,b)=1,故方程 by'+rx'=ri (7) 有整数解设x=,y=乃是(6)的任一整数解，则 为==、46+n西 (8) b b 但，g·90都是整数，因此4”出也是整数令n也 h 6,则x=,y=是(7)的一个整数解，即(6)式的任一整数解 能写成下列形状： x=x',y=4-qx′+y', (9) 其中x',y是(7)的某一整数解，反之，若x',y是(7)的任一整数 解，则由(9)式所求得的x,y是(6)的一解，这是因为由(7)，(9)可 以得出 y=4X+y=:4+16=6 故得： 定理3(6)的一切整数解可由(9)得出，只要(9)中x',y取 (7)式的一切解 在中学教科书中求(6)的解时，就是把(6)变成(8)的形状，然 后再令：-y而得到(7)，求出(7)的一切整数解后，再由 (9)求(6)的解如果由(7)还不能用观察的方法求出它的一切解 时，再把上面所说的方法应用于(7)而得到另一新的方程，求出新 的方程的一切解，再求(7)的一切解及(6)的一切解，应用这种方法 ·29·
次不定方程解法的理论根据 . 设给定一个适合下列条件的二元一次不定方程 ax + by = c, a > b > 0, ( a, b) = 1 . ( 6) 那么由第一章§1 定理 4 , 知道有整数 q1 , q′ 1 , r1 , r′ 1满足条件 a = bq1 + r1 ,0≤ r1 < b, c = bq′ 1 + r′ 1 , 0≤ r′ 1 < b .又由第一章§2 定理 3 得到( b, r1 ) = ( a, b) = 1 ,故方程 by′+ r1 x′= r′ 1 ( 7) 有整数解 .设 x = x0 , y = y0 是(6 )的任一整数解, 则 y0 = c - ax0 b = q′ 1 - q1 x0 + r′ 1 - r1 x0 b . ( 8) 但 y0 , q′ 1 - q1 x0 都是整数, 因此 r′ 1 - r1 x0 b 也是整数 .令 r′ 1 - r1 x0 b = y′ 0 ,则 x′= x0 , y′= y′ 0是 (7 )的一个整数解,即 ( 6 )式的任一整数解 能写成下列形状: x = x′, y = q′ 1 - q1 x′+ y′, ( 9) 其中 x′, y′是 (7 )的某一整数解, 反之, 若 x′, y′是( 7 ) 的任一整数 解,则由( 9) 式所求得的 x , y 是( 6) 的一解,这是因为由 ( 7) , (9 ) 可 以得出 y = q′ 1 - q1 x′+ y′= q′ 1 - q1 x + r′ 1 - r1 x b = c - ax b . 故得: 定理 3 ( 6)的一切整数解可由 (9 ) 得出, 只要 ( 9 ) 中 x′, y′取 (7 )式的一切解 . 在中学教科书中求(6 )的解时, 就是把( 6 ) 变成 ( 8 ) 的形状, 然 后再令 r′ 1 - r1 x b = y′而得到 ( 7 ) , 求出 ( 7 ) 的一切整数解后, 再由 (9 )求( 6) 的解 .如果由 ( 7 ) 还不能用观察的方法求出它的一切解 时,再把上面所说的方法应用于 ( 7) 而得到另一新的方程, 求出新 的方程的一切解,再求( 7) 的一切解及(6 )的一切解, 应用这种方法 · 29 ·
在有限次以后一定可以得到一个二元一次不定方程，而它的一切 整数解能够用观察的方法得到这因为(7)的系数不过是辗转相除 法中第一个式子的除数及余数，而由(7)得到的新的方程不过是第 二个式子的除数及余数.由辗转相除法的理论及a,b互质的条 件，有限次以后一定可以得到一个方程，其中有一个系数是1，那 么这个方程的一切解便可以用观察的方法得到从定理3可以看 出，应用这种方法一定能够把(6)的一切解求出来现在我们来看 一个例子 例3求107x+37y=25的一切整数解 解由给定的方程得 y=2507江-2x+2533x-2x+y, 37 37 其中y=25,3兰应该是整数，故得一新的不定方程 37 37y+33x=25 (10) 又 x=2537-.y+254-y+x, 33 33 仿前令x=5,4立，又得到一个新的不定方程 33 33x′+4y=25 (11) 又y=2533x=6.8x+11=6.8+y, 4 A 其中y=1子，即最后得到 x'+4y”=1 (12) 显然(12)的一切解是 x'=1-41,y”=t(1=0,±1，±2，.) 因此(11)的一切解是 x=1-41,y=6-8x+y=-2+331(1=0,±1，±2，.)， ·30·
在有限次以后一定可以得到一个二元一次不定方程, 而它的一切 整数解能够用观察的方法得到 .这因为( 7) 的系数不过是辗转相除 法中第一个式子的除数及余数,而由( 7) 得到的新的方程不过是第 二个式子的除数及余数 .由辗转相除法的理论及 a, b 互质的条 件,有限次以后一定可以得到一个方程, 其中有一个系数是 1, 那 么这个方程的一切解便可以用观察的方法得到 .从定理 3 可以看 出,应用这种方法一定能够把 (6 ) 的一切解求出来 .现在我们来看 一个例子 . 例 3 求 107 x + 37 y = 25 的一切整数解 . 解 由给定的方程得 y = 25 - 107 x 37 = - 2 x + 25 - 33 x 37 = - 2 x + y′, 其中 y′= 25 - 33 x 37 应该是整数,故得一新的不定方程 37 y′+ 33 x = 25 . (10) 又 x = 25 - 37 y 33 = - y′+ 25 - 4 y′ 33 = - y′+ x′, 仿前令 x′= 25 - 4 y′ 33 , 又得到一个新的不定方程: 33 x′+ 4 y′= 25 . (11) 又 y′= 25 - 33 x′ 4 = 6 - 8 x′+ 1 - x′ 4 = 6 - 8 x′+ y″, 其中 y″= 1 - x′ 4 , 即最后得到 x′+ 4 y″= 1 . (12) 显然(12) 的一切解是 x′= 1 - 4 t , y″= t ( t = 0, ± 1, ± 2 ,.) . 因此(11) 的一切解是 x′= 1 - 4 t, y′= 6 - 8 x′+ y″= - 2 + 33 t ( t = 0, ± 1, ± 2,.), · 30 ·