1.1.25

1.1.25 #

解答 #

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

设 $\ r_0=a\bmod b$ ,$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=0$ (此时算法终止)。

由于 $r_{n-2}=q_n\times r_{n-1} + r_n=q_n\times r_{n-1} \ (q_n=\lfloor r_{n-2}/r_{n-1}\rfloor)$ 。

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

则有

$r_{n-3}\newline =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}$

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

以此类推,$r_{n-1}$ 可以整除 $a$ 和 $b$ ,即 $r_{n-1}$ 是 $a$ 和 $b$ 的公约数

则 $r_{n-1}\le g$ 。

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

$r_0 \newline =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$

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

同理 $r_0,r_1,r_2\dots r_{n-1}$ 都可以被 $g$ 整除。

因此 $g\le r_{n-1}$

综上,$g=r_{n-1}$ ,证明完毕。