列等式： a=bq+n,0<n<b, b=n9+n,0<n<n, . (1) .2=n.14+n,0<n<n.1, a.1=qa+1+n+1,n+1=0 因为每进行一次带余数除法，余数就至少减一，而b是有限的，所 以我们最多进行b次带余数除法，总可以得到一个余数是零的等 式，即+1=0(1)式所指出的计算方法，叫作辗转相除法在西方 常把它叫做欧几里得除法，它也就是我国著名的古代数学著作《九 章算术》中提出的“更相减损术”现在我们证明 定理4若a,b是任意两个整数，则(a,b)就是(1)中最后一 个不等于零的余数，即(a,b)=rn 证由定理2,3即得 ra=(0,ra)=(ra+1,ra)） =(ra,n.1）=. =(n,b)=(a,b) 证完 由于，能够用辗转相除法直接算出，所以辗转相除法给出了求两 整数的最大公因数的实际可行的算法 由定理2,3及(1)我们还可以得到 推论4.1a,b的公因数与(a,b)的因数相同（证明留给读 者) 由以上的讨论，我们可以看到，若a,b两整数中有一为零，而 另一数不为零时，则(a,b)为不等于零的数的绝对值，若a,b两 数都不是零时，则a,b最大公因数可以由(1)实际地算出来 我们看两个例子： 例1a=-1859,b=1573,由定理1，(-1859,1573)= ·6· 列等式: 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 + rn + 1 , rn + 1 = 0 . ( 1) 因为每进行一次带余数除法,余数就至少减一, 而 b 是有限的, 所 以我们最多进行 b 次带余数除法, 总可以得到一个余数是零的等 式,即 rn + 1 = 0 .( 1) 式所指出的计算方法,叫作辗转相除法 .在西方 常把它叫做欧几里得除法 .它也就是我国著名的古代数学著作《九 章算术》中提出的“更相减损术”.现在我们证明 定理 4 若 a, b 是任意两个整数, 则( a, b) 就是 ( 1) 中最后一 个不等于零的余数,即( a, b) = rn . 证 由定理 2, 3 即得 rn = ( 0, rn ) = ( rn + 1 , rn ) = ( rn , rn - 1 ) = . = ( r1 , b) = ( a, b) . 证完 由于 rn 能够用辗转相除法直接算出, 所以辗转相除法给出了求两 整数的最大公因数的实际可行的算法 . 由定理 2, 3 及(1 )我们还可以得到 推论 4.1 a, b 的公因数与 ( a, b) 的因数相同 ( 证明留给读 者) . 由以上的讨论,我们可以看到, 若 a, b 两整数中有一为零, 而 另一数不为零时,则 ( a, b ) 为不等于零的数的绝对值, 若 a, b 两 数都不是零时,则 a, b 最大公因数可以由(1 )实际地算出来 . 我们看两个例子: 例 1 a = - 1859, b = 1573, 由定 理 1, ( - 1859, 1573 ) = · 6 ·