ACM算法竞赛——裴蜀定理

在数论中，裴蜀定理（或贝祖定理）是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。
裴蜀定理说明了对任何整数 a、b和它们的最大公约数 d ，关于未知数 x以及 y 的线性的丢番图方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

通过扩展欧几里得算法证明