欧几里得算法是计算两个数最大公因子算法。又称辗转相除法。本文将学习为什么辗转相除法可以求得两个数的最大公因子。同时也可以根据最大公因子计算两个数的最小公倍数。

文章目录

1 欧几里得算法的理论基础

设 a=qb+r， 其中 a, b, q, r 都是整数， 则

  • GCD(a, b) = GCD(b, r)

证明过程如下：

1.1 欧几里得算法（辗转相除法）

  • 欧几里得算法（辗转相除法） GCD ( a, b )
  • 输入： 整数 a, b ， 满足 a >= b >= 0 ， 且 a, b 不全为0
  • 输出： GCD(a, b)

由上面欧几里得算法的理论基础知：GCD(a, b) = GCD(b, r)

则，欧几里得算法的步骤如下：

可以由欧几里得算法计算两个数的最大公约数后，根据GCD(a,b)*LCM(a,b)=a*b 计算最小公倍数。

2 裴蜀等式（贝祖等式）

  • 对于不全为0的整数 a, b 和 d ， 方程 sa+tb=d存在整数解 s 和 t 当且仅当 GCD(a, b)|d 。
  • 方程 sa+tb=d 称作裴蜀（Bezout） 等式或贝祖等式。

证明：

  1. 充分性证明：sa+tb=GCD(a, b)可定是存在整数解的，设为 s0、 t0。若d=kGCD(a, b)=k(sa+tb),则k*s0, k*t0是方程的一个解。
  2. 必要性证明：若方程 sa+tb=d 存在整数解 s 和 t 则GCD(a, b) | (sa+tb)=d