费马定理

p 为素数

如果 $(r,p)=1$

$$r^p\equiv r(modp)$$

因为从 欧拉定理 得知 $r^{\phi (p)}\equiv 1⟹r^{p-1}\equiv 1(modp)$

如果 $(r,p)\ne 1⟹p|r$

$$r^p\equiv r\equiv 0$$

所以总有

$$r^p\equiv r(modp)$$