同余总结

同余

定义

若对于$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$

运用和板子

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

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