欧几里得算法证明

欧几里得算法

  欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式 $\gcd(a,b) = \gcd(b,a % b)$

  这是一个能够将一个大问题转化为小问题求解的算法,而这个算法的过程,本文不再赘述,主要记录这个算法正确性的证明。

要证明 $\gcd(a, b) = \gcd(b, a%b)$ 成立,即要证两个内容。

  1. $\gcd(b, a % b)$ 的答案包含 $\gcd(a, b)$ 的答案
  2. $\gcd(b, a%b)$ 的答案是 $a,b$ 的最大公约数

证明 1 成立

设 $ r $ 为 $\gcd(a, b)$ 的答案,可得下述关系:

  $\begina=xr\ b=yr\end (x, y \in Z)$, 同时由于 $ r $ 是 $a, b$ 的最大公约数,所以 $gcd(x, y) = 1$,因为如果 $x, y$ 还有公约数,那么 $ r $ 就还能增大,与预设有悖。

在 $\gcd(b, a%b)$ 中可得下述关系:

  $\begina%b = a - kb\ k = a / b\end (k \in Z) \Rightarrow a % b = a - kb = xr - yr = (x - ky)r$,整理可得

  $\beginb=yr\ a%b=(x - ky)r\end (x, y, k \in Z)$

观察上式可分析,$ b $, 与 $a%b$ 中均包含 $ r $,问题 1 证毕。

证明 2 成立

  要证明 $ r $ 在 $\gcd(b, a%b)$ 中也是最大的,由上述公式:$\beginb=yr\ a%b=(x - ky)r\end (x, y, k \in Z)$ 可得 $\gcd(y, (x - ky)) = 1$ 时, $ r $ 为最大,至于为何,与上述解释相同。

此处采用反证法,假设 $ d $ 为 $\gcd(y, (x - ky))$ 的值,那么可以得出

  $\beginy=nd\ x - ky= md\end (x, y, k, n, m \in Z)$,整理可得

  $\beginy=nd\ x=md + knd = (m + kn)d\end (x, y, k, n, m \in Z)$,由于 $\gcd(x, y) = 1$,所以 $ d $ 此时必须为 $ 1 $,才能不与初始设定相悖,故次问题 2 证毕。

  通过证明问题 1, 与问题 2可以得出辗转相除法的转移是正确的,也就证明了算法的正确性,在我漫长的使用 $__\gcd()$ 的竞赛生涯中第一次尝试证明这个算法。

代码实现

int gcd(int a, int b) {
    return (b ? gcd(b, a % b) : a);
}

拓展欧几里得算法