模数逆（2.裴枢定理）

一.裴蜀定理

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。裴蜀定理说明了对任何整数 a、b和它们的最大公约数 d ，关于未知数 x以及 y 的线性的丢番图方程（称为裴蜀等式）。

1.1 裴蜀定理的基本公式

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x、y，ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

1.2 裴蜀定理的证明

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x、y，ax+by都一定是d的倍数（容易理解）
特别地，一定存在整数x,y，使ax+by=d成立（求证？）

    设  d  =  gcd（a，b），则 d|a（表示a被d整除), d|b . 对于任意整数 x，y. 都有d|（a*x+b*y)
     
    设s为 ax+by 最小正值，令q=[a/s] (这里的q表示不大于a/s的最大整数)

    令r=a mod s= a - q*s= a - q*（ax+by)=a(1-q*x) + b*(-qy) 

    可见 r 也是a、b的线性组合，由于 r 为 a mod s 所得 ，所以   0 &