很多人都知道这个算法，但怎样得来的可能知道的不多，在此翻译一篇与大家共享：科普一下
辗转相除法主要就是采用了公式GCD(a, b) = GCD(b, a mod b) 假设a>=b
GCD 是Greatest common divisor的缩写即最大公约数。
For any nonnegative integer a and any positive integer b, GCD(a, b) = GCD(b, a mod b). Proof We shall show that GCD(a, b) and GCD(b, a mod b) divide each other, so that by equation (31.5) they must be equal (since they are both nonnegative).对于任何非负整数a和任意正数b，等式GCD(a, b) = GCD(b, a mod b) 成立。证明：通过GCD(a, b) 和GCD(b, a mod b)可以彼此相除，利用等式31.5可知它们相等(GCD(a, b)不可能为- GCD(b, a mod b)，因为它们都是非负数)。
注：We have that n | a if and only if a mod n = 0.
如果 a mod n = 0 我们就称作n | a “ |” 读作divide
We first show that GCD(a, b) | GCD(b, a mod b). If we let d = GCD(a, b), then d | a and d | b. By equation (3.8), (a mod b) = a - qb, where q为a/b 向下取整. Since (a mod b) is thus a linear combination of a and b, equation (31.4) implies that d | (a mod b). Therefore, since d | b and d | (a mod b), Corollary 31.3 implies that d | GCD(b, a mod b) or, equivalently, that GCD(a, b) = GCD(b, a mod b) (31.14)
首先证明GCD(a, b) | GCD(b, a mod b).令d = GCD(a, b)，由最大公约数的定义可知
d | a 和 d | b成立，即d | qb也成立。由等式3.8，可知a mod b 是a和b的线性组合a - qb，再由31.4得到d | (a - qb)即d | (a mod b)，由前面的d | b结合推论31.3可知 d | GCD(b, a mod b) 即GCD(a, b) | GCD(b, a mod b) (31.14)成立。
Showing that GCD(b, a mod b) | GCD(a, b) is almost the same. If we now let d = GCD(b, a mod b), then d | b and d | (a mod b). Since a = qb + (a mod b), where q = a/b, we have that a is a linear combination of b and (a mod b). By equation (31.4), we conclude that d | a. Since d | b and d | a, we have that d | GCD(a, b) by Corollary 31.3 or, equivalently, that GCD(b, a mod b) | GCD(a, b) (31.15)
同理证明(31.15) GCD(b, a mod b) | GCD(a, b)
Using equation (31.5) to combine equations (31.14) and (31.15) completes the proof. 由等式31.5结合(31.14)、 (31.15) 证明GCD(a, b) = GCD(b, a mod b)成立。
equation (3.8) a mod n=a- q*n q为a/n 向下取整
(31.3) d | a and d | b implies d | (a+b) and d | (a-b)
More generally, we have that
(31.4) d | a and d | b implies d | (ax+by) for any integers x and y.
Also, if a | b, then either |a| <=|b| or b = 0, which implies that
(31.5) a | b and b | a implies a=±b
推论Corollary 31.3
For any integers a and b, if d | a and d | b then d | GCD(a, b).
Proof This corollary follows from equation (31.4), because GCD(a, b) is a linear combination of a and b by Theorem 31.2.
Theorem 31.2 GCD(a, b)是a和b的一个线性组合
证明 a和b的最大公约数GCD(a, b)等于线性组合ax + by组成的元素集合中的最小正数值。
If a and b are any integers, not both zero, then GCD(a, b) is the smallest positive element of the set {ax + by : x, y为 Z} of linear combinations of a and b.
Proof Let s be the smallest positive such linear combination of a and b, and let
s = ax + by for some x, y Z. Let q 为 a/s向下取整.Equation (3.8)
a mod s = a - qs = a - q(ax + by) = a (1 - qx) + b(-qy),
and so a mod s is a linear combination of a and b as well. But, since a mod s < s, (注：a mod s 是a、b的线性组合，s也是a、b的线性组合且已经是最小的正数，那么a mod s 由定义必须>=0,因此只能是0)，we have that a mod s = 0(即s是a的一个因子). Therefore, s | a and, by analogous reasoning,同理 s | b. Thus, s is a common divisor of a and b即s是a，b的一个公约数, and so GCD(a, b)>= s. Equation (31.4) implies that GCD(a, b) | （ax + by）, since GCD(a, b) divides both a and b and s is a linear combination of a and b，so GCD(a, b) | s， and s > 0 imply that GCD(a, b) <=s. Combining GCD(a, b)>=s and GCD(a, b) <=s yields GCD(a, b) = s; we conclude that s is the greatest common divisor of a and b.得出结论a，b的最大公约数就是s，也就是说a，b的最大公约数就是线性组合ax + by组成的元素集合中的最小正数值。
