费马小定理
若 $p$ 为质数，$a$ 不是 $p$ 的倍数，则 $a^{p-1}\equiv 1(\mod p)$
证明：
$0<t<p,ta$ 在 $\mod p$ 下互不相同，因为如果 $t\neq k,ta\equiv ka(\mod p),t\equiv k(\mod p)$
故 $a^{p-1}(p-1)!\equiv(p-1)!(\mod p),a^{p-1}\equiv 1(\mod p)$
积性函数
任意 $\gcd(m,n)=1$，有 $f(m)f(n)=f(mn)$，则 $f(x)$ 为积性函数。特殊地，若对任意 $m,n$ 都有 $f(m)f(n)=f(mn)$，则 $f(x)$ 为完全积性函数。
注：常见的积性函数：
- $\epsilon(x)=[x=1]$
- $1(n)=1$
- $id_k(n)=n^k$
- $\sigma_k(n)=\sum_{d|n}d^k$
- $\varphi(n)$：一会要说的欧拉函数
- $\mu(n)$：以后会说的莫比乌斯函数
欧拉函数
$\varphi(n)$ 为不超过 $n$ 且与 $n$ 互素的正整数的个数。
$p 为素数\Leftrightarrow\varphi(p)=p-1$
$\sum_{d|m}\varphi\left(\frac{m}{d}\right)=m$
$$
\varphi(m)=\sum_{i=1}^m[\gcd(m,i)=1]=m-\sum_{d|m,d\ne1}\sum_{i=d}^m[\gcd(m,i)=d]
$$$$
=m-\sum_{d|m,d\ne1}\sum_{d|i}^m\left[\gcd\left(\frac{m}{d},\frac{i}{d}\right)=1\right]
$$$$
=m-\sum_{d|m,d\ne1}\varphi\left(\frac{m}{d}\right),\therefore\sum_{d|m}\varphi\left(\frac{m}{d}\right)=m
$$$\gcd(m,n)=1,\varphi(m)\varphi(n)=\varphi(mn)$
$$
\varphi(m)=\sum_{i=1}^m[\gcd(m,i)=1],\varphi(mn)=\sum_{i=1}^{mn}[\gcd(mn,i)=1]
$$$$
=\sum_{i=1}^{mn}[\gcd(m,i)=1]\cdot[\gcd(n,i)=1]
$$$$
=\sum_{i=1}^{mn}[\gcd(m,i\mod m)=1][\gcd(n,i\mod n)=1]
$$$$
=\sum_{i=1}^m\left([\gcd(m,i)=1]\sum_{j=0}^{n-1}[\gcd(n,(mj+i)\mod n)=1] \right)
$$$$
=\sum_{i=1}^m\left([\gcd(m,i)=1]\sum_{j=1}^{n}[\gcd(n,j)=1] \right)
$$$$
=\sum_{i=1}^m[\gcd(m,i)=1]\sum_{j=1}^{n}[\gcd(n,j)=1]=\varphi(m)\varphi(n)
$$因此，欧拉函数是积性函数。
欧拉定理
若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv1(\mod m)$
证明与费马小定理类似。