裴蜀定理
在数论中，裴蜀等式（英语：Bézout’s identity）或贝祖定理（Bézout’s lemma）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：
ax + by = m 有整数解时当且仅当m是d的倍数。
欧几里德原理
gcd(a , b) = gcd(b , a mod b)
我认为扩展欧几里得就是上面两个定理组合一下
求出了一组解
void exgcd(int a, int b, int &d, int &x ,int &y)
{
if ( !b )
{
d = a;
x = 1;
y = 0;
return;
}
int x1,y1;
exgcd( b , a % b , d , x1 , y1 );
x = y1;
y = x1 - ( a / b ) * y1;
return ;
}