数学 最后更新于 2025-05-02 09:05:19

规定 $\mathbf{P}$ 为质数集。 # 费马小定理 > 若 $p\in\mathbf{P},a\in\mathbf{Z},(a,p)=1$，则 $a^{p-1}\equiv1\pmod p$。 首先我们可以得知 $a,2a,3a,\cdots,(p-1)a$ 构成模 $p$ 的一个同余系，即它们在模 $p$ 意义下互不相同。 因为若 $\exist 1\le i<j<p,ia\equiv ja\pmod p$，那么因为 $(a,p)=1$，则 $p|(j-i)$，与 $0<j-i<p$ 矛盾。 那么有 $a\times2a\times3a\times\cdots\times(p-1)a\equiv1\times2\times3\times\cdots\times(p-1)\pmod p$，因此 $a^{p-1}\equiv1\pmod p$。 # 欧拉定理 > 若 $a,m\in\mathbf{N},(a,m)=1,a^{\varphi(m)}\equiv1\pmod m$。 可以发现，费马小定理就是欧拉定理在 $m\in\mathbf{P}$ 的特殊情况，于是考虑用类似的方法证明。 取 $1=r_1<r_2<\cdots<r_{\varphi(m)}=m-1$ 满足 $\forall i\in[1,\varphi(m)],(r_i,m)=1$。即 $\{r_i\}$ 为 $m$ 的一个简化剩余系。 那么，有 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 在模 $m$ 意义下互不相同，并且均与 $m$ 互质。 同样考虑若 $\exist 1\le i<j\le\varphi(m),ar_i\equiv ar_j\pmod m$，那么因为 $(a,m)=1$，则 $m|(r_j-r_i)$，与 $0<r_j-r_i<m$ 矛盾。 那么有 $ar_1\times ar_2\times\cdots\times ar_{\varphi(m)}\equiv r_1\times r_2\times\cdots\times r_{\varphi(m)}\pmod m$，因此 $a^{\varphi(m)}\equiv1\pmod m$。 # 阶 若 $a,m\in\mathbf{Z},(a,m)=1$，由欧拉定理可知，一定存在一个正整数 $k$ 使得 $a^k\equiv1\pmod m$。 而我们称满足条件的最小正整数为 $a$ 在模 $m$ 意义下的**阶**，记作 $\delta_m(a)$ 或 $\text{ord}_m(a)$。 其有几个基本性质（可以用复数辅助理解）： - 若 $m,a,k\in\mathbf{N}^*,a^k\equiv1\pmod m$，则 $\delta_m(a)|k$。 - 若 $m\in\mathbf{N}^*,a,b\in\mathbf{Z},(a,m)=(b,m)=1$，则 $\delta_m(ab)=\delta_m(a)\delta_m(b)$ 当且仅当 $(\delta_m(a),\delta_m(b))=1$。 - 若 $m\in\mathbf{N}^*,a,k\in\mathbf{Z},(a,m)=1$，则 $\delta_m(a^k)=\dfrac{\delta_m(a)}{(\delta_m(a),k)}$。 # 原根 若 $m\in\mathbf{Z}^*,g\in\mathbf{Z},(g,m)=1,\delta_m(g)=\varphi(m)$，则称 $g$ 是 $m$ 的一个原根。 即 $g^1,g^2,\cdots,g^{\varphi(m)}$ 构成 $m$ 的一个简化剩余系。 # 数论分块 核心点： - 求解 $f(g(x),n)=\sum\limits_{i=1}^n\Big(\Big\lfloor\dfrac ni\Big\rfloor\cdot g(i)\Big)$ 的问题，且 $g(x)$ 的求和效率高（如 $g(x)=x,g(x)=x^2$ 等）。 - $r=\Big\lfloor\dfrac n{\lfloor\frac nl\rfloor}\Big\rfloor$ - 多维的情况，自变量需唯一。