同余总结

同余

定义

若对于$a,b$两个整数，除以$m$的余数相等，则称$a$,$b$模$m$同余，记作$a\equiv b(mod\ m)$

基本定理和性质

• 逆元：若$a*x\equiv 1(mod\ p)$,$a$,$b$互质,则称x是a的逆元，记为$a^{-1}$
• 欧拉定理：若$a$,$m$互质，则$a^{\phi(m)}\equiv 1(mod \ m)$
• 扩展欧拉定理： $a^b\equiv a^{b\ mod\ \phi(m)+\phi(m)}(mod\ m)$
• 贝祖定理：对于任意的整数$a,b,\exists x,y,$使得$ax+by=gcd(a,b)$
• 对于方程$ax+by=c$有整数解，当且仅当$gcd(a,b)|c$

运用和板子

• 扩展欧几里得算法：可以用来解决线性的同余方程
• 逆元：可以用来解决有除法有需要取模的问题
• 欧拉定理：可以通过欧拉函数来进行降幂操作

板子仍然是去数论板子那一篇博客里面来看