[编程笔记]-Bezout's_Lemma裴蜀定理

定理

gcd(a,b)|ax+by

a、b都是是gcd(a,b)的倍数，对于任意不全为零整数x、y所以gcd(a,b)|ax+by

因此a、b能凑出来的最小的数就是它的最大公约数。

ax+by=gcd(a, b)

对于任意正整数a, b，一定存在非零整数x, y，使得ax+by=gcd(a, b)

证明：我们可以使用构造法

构造出一种方式，对于任意正整数a, b，一定存在非零整数x, y，使得ax+by=gcd(a, b)，呢么就可以证明这个公式成立了。

这个方法就是拓展欧几里得算法。
[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法

完结撒花o(￣︶￣)o