1.1.25 #

解答 #

已知：$a,b$ 皆为正整数，且 $a>b$。$g$ 是 $a,b$ 的最大公约数.

设 $\ r_0=a \bmod b$，$r_1=b \bmod r_0$ ，$r_k = r_{k-2} \bmod\ r_{k-1}$ 。

那么有 $\gcd(a,b)=\gcd(b,r_0)=\gcd(r_0,r_1)…=\gcd(r_{n-1},r_n)=r_{n-1}$ ，且 $r_n=0$ （此时算法终止），且 $n$ 是有限的。

令 $q_n=\lfloor r_{n-2}/r_{n-1} \rfloor$

有 $r_{n-2}=q_n\times r_{n-1} + r_n=q_n\times r_{n-1}$ （被除数=商✕除数+余数）。

可得 $r_{n-2}$ 能被 $r_{n-1}$ 整除。

则有

$$ \begin{aligned} r_{n-3} &= q_{n-1} \times r_{n-2} + r_{n-1}\newline &=q_{n-1}\times (q_n \times r_{n-1})+r_{n-1}\newline &=q_{n-1}\times q_n \times r_{n-1} + r_{n-1} \newline &=(q_{n-1} \times q_n +1)\times r_{n-1} \end{aligned} $$

可得 $r_{n-3}$ 也能被 $r_{n-1}$ 整除

假设对于任意自然数 $n > x > k \ge 0$, $r_x$ 可以被 $r_{n-1}$ 整除都成立 。

则对于 $r_k$ 有：

$$ \begin{aligned} r_{k} &= q_{k+2} \times r_{k+1} + r_{k+2} \end{aligned} $$

根据假设，$r_{k+1}$ 和 $r_{k+2}$ 都可以被 $r_{n-1}$ 整除，因此 $r_k$ 也可以被 $r_{n-1}$ 整除。

根据数学归纳法可以得知对于任意 $x<n$，$r_x$ 都可以被 $r_{n-1}$ 整除。（类似于反向使用第二类数学归纳法）

现在对于 $r_1$ 有：

$$ \begin{aligned} r_1 &= b \bmod r_0 \newline r_1 &=b-q_1 \times r_0 \qquad (q_1=\lfloor b/r_0\rfloor) \newline b &= r_1 + q_1 \times r_0 \end{aligned} $$

由于 $r_0$ 和 $r_1$ 都可以被 $r_{n-1}$ 整除，则 $b$ 也可以被 $r_{n-1}$ 整除。

类似地，对于 $r_0$ 有：

$$ \begin{aligned} r_0 &= a \bmod b \newline a &= r_0 + q_0 \times b \qquad (q_0 = \lfloor a/b \rfloor) \end{aligned} $$

由于 $r_0$ 和 $b$ 都可以被 $r_{n-1}$ 整除，因此 $a$ 也可以被 $r_{n-1}$ 整除。

于是得到 $r_{n-1}$ 是 $a$ 和 $b$ 的一个公约数，必然满足 $r_{n-1} \le g$。

因为 $g$ 是 $a,b$ 的最大公约数，由其性质可得： $a=mg,b=ng$ ，其中 $m,n$ 是自然数。

$$ \begin{aligned} r_0&=a \bmod b \newline &=a-q_0 \times b\qquad (q_0=\lfloor a/b \rfloor) \newline &= mg-q_0\times ng\newline &=(m-q_0\times n)g \end{aligned} $$

可得 $r_0$ 能够被 $g$ 整除。

对于 $r_1$ 有：

$$ \begin{aligned} r_1 &= b \bmod r_0 \newline &=b-q_1 \times r_0 \qquad (q_1=\lfloor b/r_0\rfloor) \end{aligned} $$

由于 $b$ 和 $r_0$ 都能被 $g$ 整除，则 $r_1$ 也能被 $g$ 整除

对于 $r_2$ 有：

$$ \begin{aligned} r_2 &= r_0 \bmod r_1 \newline &= r_0 - q_2 \times r_1 \qquad (q_2=\lfloor r_0 / r_1 \rfloor) \end{aligned} $$

由于 $r_0$ 和 $r_1$ 都可以被 $g$ 整除，因此 $r_2$ 也可以被 $g$ 整除。

假设对于任意自然数 $x < k$， $r_x=r_{x-2} \bmod r_{x-1}$ 可以被 $g$ 整除。

则对于 $r_k$ 有：

$$ \begin{aligned} r_k &= r_{k-2} \bmod r_{k-1} \newline &= r_{k-2} - q_k \times r_{k-1} \qquad (q_k=\lfloor r_{k-2} / r_{k-1} \rfloor) \end{aligned} $$

根据假设， $r_{k-1}$ 和 $r_{k-2}$ 都可以被 $g$ 整除，此时 $r_k$ 也可以被 $g$ 整除。

由第二类数学归纳法可知对于任意满足 $0 \le x \le n$ 的自然数 $x$，$r_x$ 可以被 $g$ 整除都成立。

因此 $r_{n-1}$ 可以被 $g$ 整除，则 $g\le r_{n-1}$。

综上，当且仅当 $g=r_{n-1}$ 时满足关系 $r_{n-1} \le g \le r_{n-1}$，于是 $r_{n-1}=g$ 成立，$r_{n-1}$ 是 $a$ 和 $b$ 的最大公约数。