逆定理：若d>0为a,b公因数且存在x,y使ax+by=d，则d=gcd(a,b)。 乘法逆元：若ax≡1(mod p)，则x为a模p的逆元，记x=a⁻¹；当gcd(a,p)=1时存在。 费马小定理：质数p下，若gcd(a,p)=1，则a^{p-1}≡1(mod p)，a^{p-2}≡a⁻¹(mod p)。 欧拉定理：若gcd(a,p)=1，则a^{φ(p)}≡1(mod p)；费马小定理为其特例。 扩展欧拉定理：当gcd(a,p)>1且b≥φ(p)时，a^b≡a^{b mod φ(p)+φ(p)}(mod p)。 exgcd：求解ax+by=gcd(a,b)的一组整数特解，递归至b=0得解，通解含参数k。 同余方程ax≡c(mod b)可转化为ax+by=c，用exgcd求解。