欧几里得算法

欧几里得算法，又名辗转相除法，是求最大公约数的算法。

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

基本原理

基础定义

a和b的最大公约数g是a和b的线性和中（绝对值）最小的一个，即所有形如ua + vb（其中u和v是整数）的数中（绝对值）最小的数。所有ua + vb都是g的整数倍（ua + vb = mg，其中m是整数）。

环论定义

实现

欧几里得算法

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）

a*y' + b(a-a/b*y') = a*x + b*y

原理

求解不定方程

应用

扩展欧几里得算法