【离散数学中的数据结构与算法】二欧几里得算法与裴蜀等式

╰+攻爆jí腚メ 2022-03-09 00:34 201阅读 0赞

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

> ### 文章目录 ###
> 
>  *   *  1 欧几里得算法的理论基础
>      *   *  1.1 欧几里得算法（辗转相除法）
>      *  2 裴蜀等式（贝祖等式）

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

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

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

证明过程如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]

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

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]

> 可以由欧几里得算法计算两个数的最大公约数后，根据`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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]: /images/20220309/a3ce0896f9364a978867e281195ed6f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220309/fa98ff914ba24031b2d0ce8df596e2a6.png