数论(新)

费马小定理

若 $p$ 为素数，$gcd(a,p)=1$ ，则 $a^{p-1} \equiv 1 \pmod{p}$

欧拉定理

若 $gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1\pmod m$

扩展欧拉定理

主要用于解决幂次很大时的取模

按底数 $a$ 和模数 $p$ 的关系分情况（与指数是多少无关）

1. 若 $gcd(a,p)=1$，则 $a^{b}\equiv a^{b\mod{\varphi(p)}}\pmod p$
2. 若 $gcd(a,p)\neq 1$，则

$$a^b\equiv \begin{cases} a^b, & b<\varphi(p)\\ a^{(b\mod \varphi(p))+\varphi(p)}, &b\ge \varphi(p) \end{cases} \pmod p$$