1.1.25

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

已知:$ 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}\\=q_{n-1} \times r_{n-2} + r_{n-1}\\=q_{n-1}\times (q_n \times r_{n-1})+r_{n-1}\\=q_{n-1}\times q_n \times r_{n-1} + r_{n-1} \\=(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 \\=a \bmod b \\=a-q_0 \times b\qquad (q_0=\lfloor a/b \rfloor) \\= mg-q_0\times ng\\=(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} $ ,证明完毕。

上一题 下一题