前置知识点

整除

对于整数 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

定理证明

① gcd( a, b ) = gcd( b, a )

设整数 a 的因数为 { ±a1, ±a2, …, ±an }，整数 b 的因数为 { ±b1, ±b2, …, ±bm }

最大公约数是两约数集合交集中的最大项，与集合顺序无关

故 gcd( a, b ) = gcd( b, a )

② gcd( a, b ) = gcd( |a|, |b| )

设整数 a 的约数为 { ±a1, ±a2, …, ±an }，则对任意整数 i（ 1 ≤ i ≤ n ），存在整数 q，使 a = q * ai

而 -a = (-q) * ai，故 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 )

证毕

通过以上证明，我们发现辗转相除法的本质在于不断缩小计算范围，直到无法化简(b=0)为止，此时剩下的数a(不可再分)，就是最大公因数：

a=qb+q′c+q′′d+β=(qnk)+(q′n′k)+(q′′n′′k)+βa=qb+q'c+q''d+\beta \\=(qnk)+(q'n'k)+(q''n''k)+\beta

其中，β\beta 为：e=0∗e+βe=0*e+\beta，β=e\beta=e

可写作y=ax+by=ax+b的线性格式。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 递归版辗转相除法
def gcd(a,b):
    if b==0:
        return a
    return gcd(abs(b),abs(a)%abs(b))

# 非递归
def gcd1(a,b):
    a,b=abs(a),abs(b)
    while 1:
        c=a%b
        if c==0:
            return b
        a=b
        b=c

# 更相减损术
def gcd2(a,b):
    if a==0:
        return b
    if b==0:
        return a
    a,b=abs(a),abs(b)
    while a!=b:
        if a>b:
            a=a-b
        else:
            b=b-a
    return a