公因数

对于正整数 $a$ 和 $b$,若存在正整数 $d, p, q$ 满足如下关系:

则称 $d$ 为 $a$ 和 $b$ 的一个公因数(或公约数,下略).

在 $a$ 和 $b$ 所有公因数之中最大的一个称为最大公因数(Greatest Common Divisor, GCD).
若 $d$ 为 $a$ 和 $b$ 的最大公因数,则 $p$ 与 $q$ 互质,反之亦然.

欧几里得算法

欧几里得算法,又称辗转相除法,是用于求最大公因数的一种算法. 它满足如下关系:

它的终止条件为 b = 0 ,此时 a 即为所求最大公因数. 示例代码如下:

int gcd(int a, int b) {
    if (a == 0) return a;
    else return gcd(b, a % b);
}

证明

设 $gcd(a, b) = d_1$ .
则有 $a = md_1, \space b = nd_1 \space (m, n \in \mathbb{Z^+} 且 m, n 互质 )$ .
令 $a = bq + r_1 \space (q, r_1 \in \mathbb{Z^+})$ , 则易知 $ r_1=(m-nq)d_1 $ .
此时,若需要证明 $b$ 和 $r_1$ 最大公因数为 $d_1$,则需要证明 $n$ 和 $m - nq$ 互质.
不妨设 $n$ 和 $m - nq$ 不互质.
则令 $gcd(n, m-nq) = d_2 \space (d_2 > 1) $ .
设 $ n = xd_2, \space m-nq = yd_2 $,可得 $ m = (xq+y)d_2 $ .
因为 $ d_2 \mid n, \space d_2 \mid m $
所以 $ m, n $ 存在公因数 $ d_2 $ 且 $d_2 > 1$.
所以 $ m, n $ 不互质,与前设矛盾.
所以 $n$ 和 $m - nq$ 互质.
所以 $ gcd(b, a \bmod b) = gcd(b, r_1) = d_1 = gcd(a, b) $.
证毕.


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!