辗转相除法证明

欧几里得算法的概述欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。

其计算原理依赖于下面的定理：定理：gcd(a,b) = gcd(b,a mod b)证明：a可以表示成a = kb + r，则r = a mod b假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r因此d是(b,a mod b)的公约数假设d 是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb +r因此d也是(a,b)的公约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证欧几里得算法原理Lemma 1.3.1 若a, b 且 a = bh + r, 其中h, r , 则gcd(a, b) = gcd(b, r).证明. 假设d1 = gcd(a, b) 且d2 = gcd(b, r). 我们证明d1| d2 且d2| d1, 因而可利用Proposition 1.1.3(2) 以及d1, d2 皆為正数得证d1 = d2.因d1| a 且d1| b 利用Corollary 1.1.2 我们知d1| a - bh = r. 因為d1| b, d1| r 且d2 = gcd(b, r) 故由Proposition 1.2.5 知d1| d2. 另一方面, 因為d2| b 且d2| r 故d2| bh + r = a. 因此可得d2| d1.Lemma 1.3.1 告诉我们当 a > b > 0 时, 要求a, b 的最大公因数我们可以先将 a 除以 b 所得餘数若為r, 则a, b 的最大公因数等於 b 和r 的最大公因数. 因為0r < b < a, 所以当然把计算简化了. 接著我们就来看看辗转相除法. 由於gcd(a, b) = gcd(- a, b) 所以我们只要考虑a, b 都是正整数的情况.Theorem 1.3.2 (The Euclidean Algorithm) 假设a, b 且 a > b. 由除法原理我们知存在h0, r0 使得a = bh0 + r0, 其中0r0 < b.若r0 > 0, 则存在h1, r1 使得b = r0h1 + r1, 其中0r1 < r0.若r1 > 0, 则存在h2, r2 使得r0 = r1h2 + r2, 其中0r2 < r1.如此继续下去直到rn = 0 為止. 若n = 0 (即r0 = 0), 则gcd(a, b) = b. 若n1, 则gcd(a, b) = rn - 1.証明. 首先注意若r0 0, 由於r0 > r1 > r2 > ... 是严格递减的, 因為r0 和0 之间最多仅能插入r0 - 1 个正整数, 所以我们知道一定会有nr0 使得rn = 0.若r0 = 0, 即 a = bh0, 故知 b 為 a 之因数, 得证 b 為a, b 的最大公因数. 若r0 > 0, 则由Lemma 1.3.1 知gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = ... = gcd(rn - 1, rn) = gcd(rn - 1, 0) = rn - 1.现在我们来看用辗转相除法求最大公因数的例子Example 1.3.3 我们求 a = 481 和 b = 221 的最大公因数. 首先由除法原理得481 = 2 . 221 + 39, 知r0 = 39. 因此再考虑 b = 221 除以r0 = 39 得221 = 5 . 39 + 26, 知r1 = 26. 再以r0 = 39 除以r1 = 26 得39 = 1 . 26 + 13, 知r2 = 13. 最后因為r2 = 13 整除r1 = 26 知r3 = 0, 故由Theorem 1.3.2 知gcd(481, 221) = r2 = 13.在利用辗转相除法求最大公因数时, 大家不必真的求到rn = 0. 例如在上例中可看出r0 = 39 和r1 = 26 的最大公因数是13, 利用Lemma 1.3.1 马上得知gcd(a, b) = 13.在上一节Corollary 1.2.5 告诉我们若gcd(a, b) = d, 则存在m, n 使得 d = ma + nb. 当时我们没有提到如何找到此m, n. 现在我们利用辗转相除法来介绍一个找到m, n 的方法. 我们沿用Theorem 1.3.2 的符号. 首先看r0 = 0 的情形, 此时 d = gcd(a, b) = b 所以若令m = 0, n = 1, 则我们有 d = b = ma + nb. 当r0 0 但r1 = 0 时, 我们知d = gcd(a, b) = r0. 故利用a = bh0 + r0 知, 若令m = 1, n = - h0, 则d = r0 = ma + nb. 同理若r0 0, r1 0 但r2 = 0, 则知d = gcd(a, b) = r1. 故利用a = bh0 + r0 以及b = r0h1 + r1 知r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + (1 + h0h1)b.因此若令m = - h1 且n = 1 + h0h1, 则 d = r1 = ma + nb. 依照此法, 当r0, r1 和r2 皆不為0 时, 由於d = gcd(a, b) = rn - 1 故由rn - 3 = rn - 2hn - 1 + rn - 1 知d = rn - 3 - hn - 1rn - 2. 利用前面推导方式我们知存在m1, m2, n1, n2 使得rn - 3 = m1a + n1b 且rn - 2 = m2a + n2b 故代入得d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2)a + (n1 - hn - 1n2)b.因此若令m = m1 - hn - 1m2 且n = n1 - hn - 1n2, 则 d = ma + nb.上面的说明看似好像当r0 0 时对每一个i {0, 1,..., n - 2} 要先将ri 写成ri = mia + nib, 最后才可将d = rn - 1 写成ma + nb 的形式. 其实这只是论证时的方便, 在实际操作时我们其实是将每个ri 写成mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回d = ma + nb. 请看以下的例子.Example 1.3.4 我们试著利用Example 1.3.3 所得结果找到m, n 使得13 = gcd(481, 221) = 481m + 221n. 首先我们有13 = r2 = 39 - 26 = r0 - r1. 而r1 = 221 - 5 . 39 = b - 5r0, 故得13 = r0 - (b - 5r0) = 6r0 - b. 再由r0 = 481 - 2 . 221 = a - 2b, 得知13 = 6(a - 2b) - b = 6a - 13b. 故得m = 6 且n = - 13 会满足13 = 481m + 221n.要注意这裡找到的m, n 并不会是唯一满足 d = ma + nb 的一组解. 虽然上面的推演过程好像会只有一组解, 不过只能说是用上面的方法会得到一组解, 并不能担保可找到所有的解. 比方说若令m' = m + b, n' = n - a, 则m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以m', n' 也会是另一组解. 所以以后当要探讨唯一性时, 若没有充分的理由千万不能说由前面的推导过程看出是唯一的就断言是唯一. 一般的作法是假设你有两组解, 再利用这两组解所共同满足的式子找到两者之间的关系. 我们看看以下的作法.Proposition 1.3.5 假设a, b 且 d = gcd(a, b). 若x = m0, y = n0 是 d = ax + by 的一组整数解, 则对任意t , x = m0 + bt/d, y = n0 - at/d 皆為d = ax + by 的一组整数解, 而且 d = ax + by 的所有整数解必為x = m0 + bt/d, y = n0 - at/d 其中t 这样的形式.証明. 假设x = m, y = n 是 d = ax + by 的一组解. 由於已假设x = m0, y = n0 也是一组解, 故得am + bn = am0 + bn0. 也就是说a(m - m0) = b(n0 - n). 由於d = gcd(a, b), 我们可以假设 a = a'd, b = b'd 其中a', b' 且gcd(a', b') = 1 (参见Corollary 1.2.3). 因此得a'(m - m0) = b'(n0 - n). 利用b'| a'(m - m0), gcd(a', b') = 1 以及Proposition 1.2.7(1) 得b'| m - m0. 也就是说存在t 使得m - m0 = b't. 故知m = m0 + b't = m0 + bt/d. 将m = m0 + bt/d 代回am + bn = am0 + bn0 可得n = n0 - at/d, 因此得证 d = ax + by 的整数解都是x = m0 + bt/d, y = n0 -at/d 其中t 这样的形式. 最后我们仅要确认对任意t , x = m0 + bt/d, y = n0 - at/d 皆為d = ax + by 的一组整数解. 然而将x = m0 + bt/d, y = n0 - at/d 代入ax + by 得a(m0 + bt/d )+ b(n0 - at/d )= am0 + bn0 = d, 故得证本定理.利用Proposition 1.3.5 我们就可利用Example 1.3.4 找到13 = 481x + 221y 的一组整数解x = 6, y = - 13 得到x = 6 + 17t, y = - 13 - 37t 其中t 是13 = 481x + 221y 所有的整数解.欧几里得算法设计辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：1. 若r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)2. a 和其倍数之最大公因子为a。

辗转相除法的证明
辗转相除法的证明
设两数为a、b(b＜a)，求它们最⼤公约数的步骤如下：⽤b除a，得a＝bq＋r（0≤r＜b）（q是这个除法的商）。

若r=0,则b 是a和b的最⼤公约数。

若r≠0,则继续考虑。

⾸先，应该明⽩的⼀点是任何 a 和 b 的公约数都是 r 的公约数。

要想证明这⼀点，就要考虑把 r 写成 r=a-bq。

现在，如果a 和 b 有⼀个公约数 d，⽽且设 a=sd , b=td, 那么 r = sd-tdq = (s-tq)d。

因为这个式⼦中，所有的数（包括 s-tq )都为整数，所以r 可以被 d 整除。

对于所有的 d 的值，这都是正确的；所以 a 和 b 的最⼤公约数也是 b 和 r 的最⼤公约数。

因此我们可以继续对 b 和 r 进⾏上述取余的运算。

这个过程在有限的重复后，可以最终得到 r=0 的结果，我们也就得到了 a 和 b 的最⼤公约数。

辗转相除法及其原理辗转相除法是⼀种⽤于计算两个整数最⼤公约数的算法，核⼼是运⽤了 gcd( a, b ) = gcd( b, a mod b ) 这⼀公式（其中 b != 0 ）在详细介绍辗转相除法之前我想先介绍⼏个概念但如果你仅想观看代码，那么请点击如果你仅想了解 gcd( a, b ) = gcd( b, a % b ) 的证明，请点击整除对于整数 a 和整数 b（ b ≠ 0 ），若存在整数 q，使得 a = q * b，那么称 a 能被 b 整除例如 14 = 2 * 7，那么 14 能被 7 整除约数与倍数若整数 a 能够被整数b整除，则称 b 是 a 的约数（因数），a 是 b 的倍数例如 14 能够被 7 整除，那么 7 就是 14 的约数，14 就是 7 的倍数公约数若整数 d 既是整数 a 的约数，也是整数 b 的约数，那么 d 是 a, b 的公约数例如 7 即是 14 的约数，也是 21 的约数，那么 7 是 14 与 21 的公约数最⼤公约数公约数中最⼤的整数便称为最⼤公约数，整数 a 与整数 b 的最⼤公约数记为 gcd( a, b )，也记为 ( a, b )例如 14 与 21 的公约数有 { ±1，±7 }，其中整数 7 是最⼤的公约数，那么 gcd( 14, 21 ) = 7辗转相除法这⾥先给出⼏个定理，证明过程最后再叙述① gcd( a, b ) = gcd( b, a )② gcd( a, b ) = gcd( |a|, |b| )③ gcd( a, 0 ) = |a|, 其中 a ≠ 0， 即 0 和任意整数 a 的最⼤公约数均为 |a|④ 设 a, b, c, q 是四个整数，若有 a = q * b + c，则 gcd( a, b ) = gcd( b, c )通俗地说，若 c 是 a 除以 b 的余数，那么 a 和 b 的最⼤公约数等于 b 和 c 的最⼤公约数有了上述那些定理，我们便有了求两个数最⼤公约数的⽅法：例如求 15 和 21 的最⼤公约数我们知道，15 的约数有 { ±1，±3，±5，±15 }，21 的约数有 { ±1，±3，±7，±21 }那么 15 和 21 的公约数为 { ±1，±3 }，最⼤公约数是 3，即 gcd( 15, 21 ) = 3运⽤之前提到过的那些定理我们发现 15 = 0 * 21 + 15, 那么 gcd( 15, 21 ) = gcd( 21, 15 )⼜ 21 = 1 * 15 + 6 , 那么 gcd( 21, 15 ) = gcd( 15, 6 )⼜ 15 = 2 * 6 + 3，那么 gcd( 15, 6 ) = gcd( 6, 3 )⼜ 6 = 2 * 3 + 0，那么 gcd( 6, 3 ) = gcd( 3, 0 )⼜ gcd(3, 0 ) = 3，故 gcd( 15, 21 ) = 3总结⼀下，求整数 a 和整数 b 的最⼤公约数的⽅法取整数 a 和整数 b 的绝对值if b 的值为 0gcd( a, b ) = aelsegcd( a, b ) = gcd( b, a mod b )代码（c语⾔）/*求a与b的最⼤公约数递归*/int gcd(int a,int b){//a和b同时为0时⽆法求出最⼤公约数if(a==0 && b==0) return -1;if(a<0) a=-a;if(b<0) b=-b;if(b==0) return a;else return gcd(b,a%b);}/*求a与b的最⼤公约数⾮递归*/int gcd(int a,int b){//a和b同时为0时⽆法求出最⼤公约数if(a==0 && b==0) return -1;if(a<0) a=-a;if(b<0) b=-b;int c;while(b!=0){c=a%b;//求余数a=b;b=c;}return a;}定理证明① gcd( a, b ) = gcd( b, a )设整数 a 的因数为 { ±a1, ±a2, …, ±a n }，整数 b 的因数为 { ±b1, ±b2, …, ±b m }最⼤公约数是两约数集合交集中的最⼤项，与集合顺序⽆关故 gcd( a, b ) = gcd( b, a )② gcd( a, b ) = gcd( |a|, |b| )设整数 a 的约数为 { ±a1, ±a2, …, ±a n }，则对任意整数 i（ 1 ≤ i ≤ n ），存在整数 q，使 a = q * a i ⽽ -a = (-q) * a i，故 a 的约数均为 -a 的约数，同样地， -a 的约数也为 a 的约数故 a, -a, |a| 的约数集合相同，同理 b, -b, |b| 的约数集合也相同⽽最⼤公约数是两约数集合的交集中的最⼤项，故 gcd( a, b ) = gcd( |a|, |b| )③ gcd( a, 0 ) = |a|, 其中 a ≠ 0因为 a 的最⼤约数是 |a|⽽任意⾮ 0 整数都是 0 的约数，即 0 = 0 * n（ n ≠ 0 ）故 gcd( a, 0 ) = |a|④设 a, b, c, q 为四个整数，若有 a = q * b + c，则 gcd( a, b ) = gcd( b, c )（Ⅰ）设 d’ = gcd( a, b )，d” = gcd( b, c )故有整数 q1, q2, 使得 a = q1 * d’，b = q2 * d’将上⾯两式代⼊ a = q * b + c 有c = a - q * b = q1 * d’ - q * q2 * d’ = ( q1 - q * q2 ) * d’因为 q, q1, q2 均是整数，故 c 能被 d’ 整除，故 d’ 也是 c的约数故 d’ 也是 b 与 c 的公约数，即有 d’ ≤ gcd( b, c ) = d”（Ⅱ）同理有整数 q3, q4，使得 b = q3 * d”, c = q4 * d”将上⾯两式代⼊ a = q * b + c 有a = q * q3 * d” + q4 * d” = ( q * q3 + q4 ) * d”因为 q, q3, q4 均是整数，故 a 能被 d” 整除，故 d” 也是 a 的约数故 d” 也是 a 和 b 的公约数，即有 d” ≤ gcd( a, b ) = d’（Ⅲ）由上述知 d’ ≤ d” 且 d” ≤ d’故 d’ = d”，即 gcd( a, b ) = gcd( b, c )证毕。

求最大公约数的方法辗转相除法证明全文共四篇示例，供读者参考第一篇示例：辗转相除法是求解最大公约数的一种有效方法，也叫做欧几里德算法。

其基本思想是通过反复地用较大数除以较小数，然后用除数去除余数，一直重复这个过程，直到余数为0为止。

最终能够得到这两个数的最大公约数。

下面我们来详细地介绍辗转相除法的原理和证明过程。

假设有两个正整数a和b，其中a>b，我们要求它们的最大公约数。

首先我们用a除以b，得到商q和余数r，即a = q*b + r。

接着我们将b赋值给a，r赋值给b，然后再次用b去除以r，得到商q1和余数r1，即b = q1*r + r1。

如此循环下去，直到r1等于0为止。

那么此时b就是a和b的最大公约数。

下面我们用数学归纳法来证明辗转相除法的正确性。

设a=k*b+r，其中k和r是整数。

若d是a和b的一个公约数，则d也是b和r的公约数，反之亦然。

因此a和b的公约数集合等于b和r的公约数集合，即gcd(a, b) = gcd(b, r)。

现在我们假设b和r的最大公约数是d。

根据辗转相除法的步骤，可以得到以下等式：b = q1*r + r1r = q2*r1 + r2r1 = q3*r2 + r3...最终我们会得到r(n-1) = qnrn，其中rn是0。

根据这些等式，我们可以得出以下结论：r(n-2) = r(n-3) - qn-1*r(n-2)r(n-3) = r(n-4) - qn-2*r(n-3)...rn = r1 - q2*r将这些等式带入最后的等式b = q1*r + r1，可以得出以下结论：d|r(n-2) = d|r(n-3) = ... = d|r1 = d|b所以最大公约数d同时也是a和b的最大公约数。

通过以上的推导和证明，我们可以得出结论：辗转相除法能够有效地求解两个数的最大公约数。

这个算法简单易懂，而且效率非常高，适用于各种情况。

在实际运用中，辗转相除法是一个非常重要的数学工具。

n能被b整除，并且r也能被b整除，则由推论1得：qn也能被b整除
由推论2得：qn+r也能被b整除
而m=qn+r，即m也能被b整除，所以a=b
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429,
pascal代码（递归）
求两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
其中“a mod b”是指取 a ÷ b 的余数。
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步。
[编辑] 虚拟码
这个算法可以用递归写成如下:
function gcd(a, b) {
if b<>0
return gcd(b, a mod b);
else
[编辑] 算法
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤r＜b）
例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322

辗除法辗除法（zhǎnchúfǎ）——辗转相除法，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。

它是已知最古老的算法，其可追溯至3000年前。

它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

它并不需要把二数作质因子分解。

证明：设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a=bq......r 1(0≤r)。

若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。

其最后一个非零余数即为(a，b)。

[编辑] 算法辗转相除法是利用以下性质来确定两个正整数a 和 b 的最大公因子的：1. 若r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)2. a 和其倍数之最大公因子为a。

另一种写法是：1. a ÷ b，令r为所得余数（0≤r<b）若r = 0，算法结束；b 即为答案。

2. 互换：置a←b，b←r，并返回第一步。

[编辑] 虚拟码这个算法可以用递归写成如下:functiongcd(a, b) {if b<>0returngcd(b, a mod b);elsereturn a;}或纯使用循环:functiongcd(a, b) {define r as integer;while b ≠ 0 {r := a mod b;a := b;b := r;}return a;}pascal代码（递归）求两数的最大公约数functiongcd(a,b:integer):integer;beginif b=0 then gcd:=aelsegcd:=gcd (b,a mod b);end ;其中“a mod b”是指取a ÷ b 的余数。

辗转相除法
1．辗转相除法
【知识点的知识】
1、辗转相除法的来源：
辗转相除法，又名欧几里德算法，是求两个正整数之最大公因子的算法．它是已知最古老的算法，其可追溯至3000 年前．这种算法，在中国则可以追溯至东汉出现的《九章算术》．
设两数为a、b（a＞b），求a 和b 最大公约数（a，b）的步骤如下：用a 除以b，得a÷b＝q…r1（0≤r1）．若
r1＝0，则（a，b）＝b；若r1≠0，则再用b 除以r1，得b÷r1＝q…r2 （0≤r2）．若r2＝0，则（a，b）＝r1，若
r2≠0，则继续用r1 除r2，…如此下去，直到能整除为止．其最后一个非零除数即为（a，b）．
2、原理：
设两数为a、b（b＜a），用gcd（a，b）表示a，b 的最大公约数，r＝amodb 为a 除以b 以后的余数，k 为a 除
以b 的商，即a÷b＝k…r．辗转相除法即是要证明gcd（a，b）＝gcd（b，r）．
第一步：令c＝gcd（a，b），则设a＝mc，b＝nc
第二步：根据前提可知r＝a﹣kb＝mc﹣knc＝（m﹣kn）c
第三步：根据第二步结果可知c 也是r 的因数
第四步：可以断定m﹣kn 与n 互质[否则，可设m﹣kn＝xd，n＝yd，（d＞1），则m＝kn+xd＝kyd+xd＝（ky+x）d，则a＝mc＝（ky+x）dc，b＝nc＝ycd，故a 与b 最大公约数成为cd，而非c，与前面结论矛盾]
从而可知gcd（b，r）＝c，继而gcd（a，b）＝gcd（b，r）．
1/ 1。

辗转相除法原理辗转相除法，又称为欧几里得算法，是一种用来求两个正整数的最大公约数的方法。

它的原理简单易懂，而且在实际应用中具有很高的效率和准确性。

本文将详细介绍辗转相除法的原理及其应用。

辗转相除法的原理是基于以下定理，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

设两个正整数为a和b（a>b），则它们的最大公约数记为gcd(a, b)。

根据上述定理，可以得出以下递推关系式，gcd(a, b) = gcd(b, a mod b)，其中“a mod b”表示a除以b的余数。

具体来说，辗转相除法的步骤如下，首先将a除以b，得到商q和余数r，即a = b q + r。

然后将b赋值给a，将r赋值给b，继续进行相同的除法运算，直到余数为0为止。

此时，b即为最大公约数gcd(a, b)。

辗转相除法的优点在于它的迭代过程非常简单，而且每一步都能够有效地减小问题的规模。

因此，即使对于非常大的整数，辗转相除法也能够在较短的时间内得到最大公约数。

辗转相除法不仅可以用来求两个整数的最大公约数，还可以推广到求多个整数的最大公约数。

具体做法是先求出前两个数的最大公约数，然后再将这个最大公约数与第三个数求最大公约数，以此类推，直到所有的数都求出最大公约数为止。

在实际应用中，辗转相除法被广泛地应用于数论、密码学、计算机算法等领域。

例如，在RSA公钥加密算法中，需要大素数的乘积，而辗转相除法可以用来验证两个大素数是否互质。

又如，在计算机程序设计中，辗转相除法可以用来简化分数的运算，求解线性同余方程等。

总之，辗转相除法作为一种简单而有效的求最大公约数的方法，具有广泛的应用前景。

它的原理简单易懂，而且在实际应用中具有很高的效率和准确性。

希望本文对辗转相除法的原理及其应用有所帮助。

原理及其详细证明对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b 整除，b为a的因子，a为b的倍数。

如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。

推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b因为：a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1 所以：a=b辗转相除法是用来计算两个数的最大公因数如果q 和r 是m 除以n 的商及余数，即m=nq+r，则gcd(m,n)=gcd(n,r)。

证明是这样的: 设a=gcd(m,n)，b=gcd(n,r)证明：∵a为m,n的最大公约数。

∴m能被a整除，且n也能被a整除，∴由推论1得：qn也能被a整除，∴由推论2得：m-qn也能被a整除，又∵m-qn=r，∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）∵b为n和r的最大公约数，a为n和r的公约数∴a≤b，同理∵b为n, r的最大公约数，∴n能被b整除，且r也能被b整除，∴由推论1得：qn也能被b整除，∴由推论2得：qn+r也能被b整除，又∵m=qn+r，∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）∵a为m,n的最大公约数，b为m和n的公约数，∴b≤a，由以上可知：a≤b与b≤a同时成立，故可得a=b，证毕。

什么叫做辗转相除法？辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。

它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

示例：123456 和7890 的最大公因数是6，这可由下列步骤（其中，“a mod b”是指取a ÷b 的余数）看出：另一种求两数的最大公约数的方法是更相减损法。

扩展资料：更相减损法与辗转相除法：1、两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

2、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

更相损减法在两数相差较大时，时间复杂度容易退化成O(N)，而辗转相除法可以稳定在O(logN)。

但辗转相除法需要试商，这就使得在某些情况下，使用更相损减法比使用辗转相除法更加简单。

而stein算法便由此出现。

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a,b）来表示a和b的最大公约数。

有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。

（证明过程请参考其它资料）例：求15750 与27216的最大公约数。

解：∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）∵2898=1386×2+126 ∴（2898，1386）=（1386，126）∵1386=126×11 ∴（1386，126）=126所以（15750，27216）=216辗转相除法比较适合用来求两个比较大的数的最大公约数。

(ⅳ)
若
2
|
a，2
|
b，
则
(a,
b)
(|
a
2
b
|,
b)
。
11
第二节 2 辗转相除法
《初等数论》 第一章 整数的可除性
在实际计算过程中，若再灵活运用最大公约数的性质（例 如第三节定理 4 的推论），则可使得求最大公约数的过程更 为简单。
12
第二节 2 辗转相除法
《初等数论》 第一章 整数的可除性
由归纳法知式(2)对一切 n 3 成立。证毕。
5
第二节 2 辗转相除法
《初等数论》 第一章 整数的可除性
定理 1.(Lame) 设 a, bN，a > b，使用在式(1)中的记 号，则 n < 5log10b。
证明: 在式(1)中，rn 1，qn + 1 2，qi 1（1 i n），
因此 rn 1 = F2 ，
可知式(2)成立。
4
第二节 2 辗转相除法
《初等数论》 第一章 整数的可除性
假设式(2)对于所有的整数 k n（n 3）成立，即
Fk > k 2，k n，
则 Fn + 1 = Fn Fn 1 > n 2 n 3 = n 3( 1)
= n 3 2
=
n
1
，
即当 k = n 1 时式(2)也成立。
rn 1 = rnqn + 1 。
2
第二节 2 辗转相除法
由于 b 是固定的，而且
《初等数论》 第一章 整数的可除性
|b| > r1 > r2 > ，
所以式(1)中只包含有限个等式。
下面，我们要对式(1)所包含的等式的个数，即要做的 带余数除法的次数进行估计。

欧⼏⾥得算法（辗转相除法）辗转相除法是⽤来计算两个整数的最⼤公约数。

假设两个整数为a和b，他们的公约数可以表⽰为gcd(a,b)。

如果gcd(a,b) = c,则必然a = mc和b = nc。

a除以b得商和余数，余数r可以表⽰为r = a - bk，k这⾥是系数。

因为c为a和b的最⼤公约数，所以c也⼀定是r的最⼤公约数，因为r = mc - nck = (m-nk)c。

因此gcd(a,b) = gcd(b,r)，相当于把较⼤的⼀个整数⽤⼀个较⼩的余数替换了，这样不断地迭代，直到余数为0，则找到最⼤公约数。

举例两个整数为1071和462：第⼀步：1071 / 462 = 2 * 462 + 147第⼆步：462 / 147 = 3 * 147 + 21第三步：147 / 21 = 7 * 21 + 0此时余数为零，则21为两个数的最⼤公约数。

贝祖公式表明对于任意两个整数a和b，都可以找到⼀对可为负的整数x和y，可以使等式xa + yb = m，其中m为a和b的最⼤公约数，合理性稍加思考可得。

如果m为1说明a和b互素。

所以在互素的情况下，xa + yb = 1。

这个等式对于求乘法逆元有很⼤的帮助。

那么如何通过贝祖公式及扩展欧⼏⾥得算法来求乘法逆元呢？举⼀个例⼦来描述什么是乘法逆元。

如果ab mod m = 1，或者可以表⽰为ab ≡ 1 mod m，这⾥b就是a关于模数m的乘法逆元。

计算乘法逆元的⽅法就是扩展欧⼏⾥得算法，以下通过⼀个例⼦来帮助理解：假设我们要求3 关于模26的乘法逆元(隐含了3和26的最⼤公约数为1，即互素)。

当a = 3，b = 26，则根据贝祖公式，存在整数x和y，3x + 26y = 1。

思路就是等号两边同时mod 26，等式则变成(3x + 26y) mod 26 = 1 mod 26，根据模运算的性质(a + b) mod m = (a mod m + b mod m) mod m。

辗转相除法判断重因式全文共四篇示例，供读者参考第一篇示例：辗转相除法是一种常用的数学方法，用于求两个数的最大公约数。

这种方法可以帮助我们找到两个数中最大的可以同时整除的数，也就是最大公约数。

而辗转相除法判断重因式是在求两个数的最大公约数的过程中，如果余数为0，则证明已经找到了最大公约数，同时也找到了最最小公倍数。

辗转相除法的步骤非常简单。

我们将较大的数除以较小的数，然后用较小的数去除以上一步的余数，一直重复这个过程，直到余数为0。

当余数为0时，当前的除数就是最大公约数。

我们要求96和72的最大公约数。

首先我们将96除以72，得到1余24，再将72除以24，得到3余0，此时余数为0，所以最大公约数为24。

辗转相除法不仅可以用来求最大公约数，也可以用来判断是否存在重因式。

所谓重因式，是指两个数除以它们的最大公约数之后的商相同，也就是说它们能够被最大公约数整除得到相同的结果。

当两个数存在重因式时，我们可以通过辗转相除法判断出来。

如果两个数存在重因式，那么它们的最大公约数一定不为1。

因为如果最大公约数为1，那么两个数就没有公因数，也就不存在重因式。

以12和18为例，它们的最大公约数为6，而12除以6得到2，18除以6也得到3，所以12和18不存在重因式。

再以15和25为例，它们的最大公约数为5，12除以5得到3，18除以5得到5，所以15和25存在重因式。

虽然辗转相除法判断重因式是一种简单的方法，但在实际应用中却有着很大的作用。

在数学领域、工程领域甚至生活中都可以发现这种现象。

通过这种方法可以更好地理解数学规律，解决实际问题。

辗转相除法判断重因式是一种简单实用的数学方法，通过找到两个数的最大公约数，判断它们是否存在重因式，进而解决问题。

在今后的学习和工作中，可以多加运用这种方法来提高数学水平和解决问题的能力。

第二篇示例：辗转相除法是一种常用的算术方法，用来求两个数的最大公因数。

而辗转相除法判断重因式则是在辗转相除法的基础上，判断一个数是否有重因式。

辗转相除证明
辗转相除法原理证明如下:
先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数。

这样逐次用后一个数去除前一个余数，直到余数是0为止。

那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。

例如求1515和600的最大公约数，第一次：用600除1515，商2余315；第二次：用315除600，商1余285；第三次：用285除315，商1余30；第四次：用30除285，商9余15；第五次：用15除30，商2余0。

1515和600的最大公约数是15。

辗转相除法是求两个数的最大公约数的方法。

如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。

这样依次下去，直到最后一个数为止。

最后所得的一个最大公约数，就是所求的几个数的最大公约数。

辗转相除法，是由欧几里德算法而来。

其基本原理如下：如果要求两个正整数a和b（假设a>b，其实这并不影响求解算法）的最大公约数，可以表示成下面的式子：a=b×q+r （1）其中，q表示a除以b所得的商，r表示余数。

辗转相除法原理分析1、辗转相除法求最⼤公约数int a, b, c;printf("请输⼊两个整数（逗号隔开）:");scanf("%d,%d", &a, &b);c = a%b;while (c != 0){a = b;b = c;c = a%b;}互质是公约数只有1的两个整数，叫做互质整数（⾮负）。

公约数只有1的两个⾃然数，叫做互质⾃然数（即指⾮负整数。

）后者是前者的特殊情形。

【公约数和公倍数都是针对整数⽽⾔的!!】辗转相除法证明叙述：a和b两个正整数，如果a>ba/b .… …. 余数为R1b/R1 .… …. 余数为R2R1/R2 .… …. 余数为R3R2/R3 ..… ….余数为R4…. ….R(n-2)/R(n-1)……余数为Rn当Rn为零的时候，R(n-1)⼀定是最⼤公约数。

辗转相除法证明需要证明满⾜两个条件：已知条件：a和b两个正整数，如果a>b,且a/b=0,则a和b的最⼤公约数⼀定为b。

第⼀个条件证明：为什么Rn最后⼀定会等于0？原因1：任意两个数，可以是同奇同偶/以奇⼀偶，辗转相除法，主要是除数和余数的计算同偶，在辗转相除过程中，余数必为偶数。

最终余数会变为2，从⽽任意⼀个数都/可以被2整除同奇，则辗转相除过程中，余数必为偶数。

最终余数会变为1，从⽽任意⼀个数都可以被1整除⼀奇⼀偶，辗转过程中，余数必为奇数，最终会变为1 ，从⽽任意⼀个数都可以被1整除原因2：因为余数都要⼩于除数，随着辗转相除的进⾏，除数和余数越来越⼩，为何辗转相除法到最后余数⼀定为0⽽每⼀次的除数⼜分别等于上⼀次的余数，所以，总有那么⼀个时刻，余数会等于0。

第⼆个条件证明：为什么a/b和b/R1和R2/R3和R(n-2)/R(n-1)的最⼤公约数相等？设两数为a、b(a>b)，⽤gcd(a,b)表⽰a，b的最⼤公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=k.......r。

∴1387 × 73 − 162 × 625 = 1.
另解:由等式9=4 × 2+1起逐步回代,得 1=9-4 × 2=9-4 ×(11-9)=5 × 9-4 × 11=5 ×(20-11)-4 × 11 =5 × 20-9 ×11=5 × 20-9 × (71 − 3 × 20) = 32 × 20 − 9 × 71 =32 ×(91-71) − 9 × 71 = 32 × 91 − 41× 71 = 32 × 91 − 41× (162 − 91) = 73 × 91 − 41×162 = 73 × (1387 − 8 × 162) − 41× 162 = 73 ×1387 − 625 ×162. ∴1387 × 73 − 162 × 625 = 1.
Q Q0 = 0, Q1 = 1, ∴ Q2 = q2Q1 + Q0 = 1×1 + 0 = 1, Q3 = q3Q2 + Q1 = 1×1 + 1 = 2, Q4 = q4Q3 + Q2 = 3 × 2 + 1 = 7, Q5 = q5Q4 + Q3 = 1× 7 + 2 = 9, Q6 = q6Q5 + Q4 = 1× 9 + 7 = 16, Q7 = q7Q6 + Q5 = 4 ×16 + 9 = 73.
解:125=17 × 7+6,q1 = 7, r1 = 6, 17 = 6 × 2 + 5, q2 = 2, r2 = 5, 6 = 5 ×1 + 1, q3 = 1, r3 = 1, 5 = 1× 5, q4 = 5, r4 = 0, ∴ (125,17) = 1.
Q aQk − bPk = (−1) 又Q0 = 0, Q1 = 1,

欧⼏⾥得算法及其证明在数学中，辗转相除法，⼜称欧⼏⾥得算法，是求最⼤公约数的算法。

辗转相除法市⼀中递归算法，每⼀步计算的输出值就是下⼀步计算时的输⼊的值。

设k表⽰步骤数（从 0 开始计数），算法计算过程如下。

每⼀步的输⼊都是前两次计算的⾮负余数r k−1和r k−2。

因为每⼀步计算出的余数都在不断减⼩，所以，r k−1<r k−2。

在第k步中，算法计算出满⾜已下等式的商q k和余数r k：r k−2=q k r k−1+r k其中 0≤r k<r k−1。

也就是r k−2要不断减去r k−1直到⽐r k−1⼩。

为求简明，以下只说明如何求两个⾮负整数a和b的最⼤公约数（负数的情况是简单的）。

在第⼀步计算时 (k=0)，设r−2和r−1分别等于a和b，第⼆步(k=1) 时计算r−1（即b）和r0（第⼀步计算产⽣的余数）相除产⽣的商和余数，以此类推。

整个算法可以⽤如下等式表⽰：a=q0b+r0b=q1r0+r1r0=q2r1+r2r1=q3r2+r3⋯如果有a<b，算法的第⼀步实际上会把两个数字交换，因为这时a除以b所得的商会等于 0，余数r0则等于a。

然后，算法的第⼆步便是把b除以a，再计算所得之商和余数。

所以，对于k≥0 总有r k≤r k−1，即运算的每⼀步中得出的余数⼀定⼩于上⼀步计算的余数。

由于每⼀步的余数都在减⼩并且不为负数，必然存在第N步是r N等于 0 使算法终⽌，r N−1就是a和b的最⼤公约数。

其中N不可能⽆穷⼤，因为在r0和 0之间只有有限个⾃然数。

正确性的证明：辗转相除法的正确性可以分成两步来证明。

在第⼀步，证明算法的最终结果r N−1同时整除a和b。

因为它是⼀个公约数，所以必然⼩于或等于最⼤公约数g。

在第⼆步，证明g能整除r N−1。

所以g⼀定⼩于或等于r N−1。

两个不等式只在r N−1=g时同时成⽴。

具体证明如下。

证明r N−1同时整除a和b：余数r N=0，r N−1∣r N−2:r N−2=q N r N−1因为r N−1∣r N−2，所以r N−1∣r N−3：r N−3=q N−1r N−2+r N−1同理可证r N−1可以整除所有之前步骤的余数，包括a和b,即r N−1是a和b的公约数，r N−1≤g。