初等数论

l1ng21y12026 · 2025-10-22 18:08:37 · 算法·理论

初等数论

定义

完全剩余系

当 m 个整数两两 \bmod m 不同余时，即构成模 m 的完全剩余系。

一个例子是 \{0,1,\dots,m-1\}。

当将 m 的完全剩余系中每个元素乘 a,(a,m)=1 时，得到的集合依然是 m 的完全剩余系。考虑反证法，如果出现两个相同元素，ax\equiv ay\pmod m,x\not \equiv y\pmod m，那么有 a(x-y)\equiv 0\pmod m 显然矛盾。

既约剩余系

也称“缩系”或“简化剩余系”，指 m 的完全剩余系中与 m 互质的数组成的子集。

多项式的根

令 f(x) 是整系数 n 次多项式，若 f(g_i)=0，则令 f 的根为 g_1\dots g_n。

在模意义下定义为：使 f(g_i)\equiv 0\pmod m，令 f 的根为 g_1\dots g_n。

群

群是一个集合 G，连同一种运算（比如加法"+"或乘法"·"），满足以下四个基本性质（群公理）：

封闭性：对于任意 a, b \in G，运算结果 a \cdot b 也属于 G。
结合律：对于任意 a, b, c \in G，有 (a \cdot b) \cdot c = a \cdot (b \cdot c)。
单位元：存在一个唯一元素 e \in G，使得对于任意 a \in G，有 a \cdot e = e \cdot a = a。
逆元：对于任意 a \in G，存在一个唯一元素 b \in G，使得 a \cdot b = b \cdot a = e。这个 b 记为 a^{-1}。

群中元素的个数称为群的阶，记为 |G|。

例子：

所有整数 \mathbb{Z} 在加法下构成一个群。单位元是 0，元素 a 的逆元是 -a。
所有非零实数 \mathbb{R} \setminus \{0\} 在乘法下构成一个群。单位元是 1，元素 a 的逆元是 1/a。

阿贝尔群（交换群）

如果一个群还满足第五条性质：

交换律：对于任意 a, b \in G，有 a \cdot b = b \cdot a。

那么这个群就被称为阿贝尔群。

上面两个例子都是阿贝尔群。一个非阿贝尔群的例子是矩阵乘法（一般不满足交换律）。

有限群

如果一个群 G 包含的元素个数是有限的，那么这个群就是有限群。

定理

Theorem.1 费马小定理

a^{p-1}\equiv 1\pmod p,p\in Prime,(a,p)=1

证明：

构造 p 的完全剩余系 \{0,1,\dots,p-1\}，由于 (a,p)=1，\{0,a,\dots,a(m-1)\} 也是 p 的完全剩余系。

根据完全剩余系内的元素取恰好一遍 0\sim p-1，有 1\times \dots \times (p-1)\equiv a\times \dots \times a(p-1)\pmod m。

易知 ((p-1)!,p)=1 可以两边约去 (p-1)!，即 a^{p-1}\equiv 1\pmod p。

关于 ac\equiv bc\pmod m，是否能约去 c 的问题。能约去 c 当且仅当 (m,c)=1。

其相当于 m|c(a-b)，显然若 (c,m)\ne 1，只能推出 \frac mc |(a,b) 即 a\equiv b\pmod {\frac mc}。不能推出 m|(a,b)。

Theorem.2 欧拉定理

a^{\varphi(m)}\equiv 1\pmod m,(a,m)=1

证明：

构造 m 的既约剩余系，c_1,c_2,\dots c_{\varphi(m)}，由于 (a,m)=1，故 ac_1,ac_2,\dots ac_{\varphi(m)} 也是 m 的既约剩余系。

同 Theorem.1，有 \prod c_i\equiv \prod ac_i\pmod m，共 \varphi(m) 项，消去 c 得证。

欧拉定理的实质是拉格朗日定理的推论：一个有限群的任意元素的阶都整除该群的阶。

模 m 的既约剩余系是一个有限阿贝尔群。其群的阶，即群大小为 \varphi(m)，拉格朗日定理指出对于群中元素 a，\delta_m(a)|\varphi (m)。其中 (a,m)=1。

Theorem.3 威尔逊定理

p\in Prime\Leftrightarrow(p-1)!+1 \equiv 0\pmod p

正定理证明：

引理：令 f(x),g(x) 是整系数 n 次多项式，其根分别为 f_1\dots f_n 和 g_1\dots g_n。

若 [x^n]f(x)= [x^n]g(x) 那么 f(x)=g(x)。因式分解 f,g 即可，不作严谨证明。

根据引理，令 f(x)=\prod_{i=1}^{p-1}(x-i),g(x)=x^{p-1}-1。注意此处“根”均指在模 p 意义下的根。

易得 f(x) 的根为 1,\dots,p-1。根据费马小定理，g(x) 的根也为 1,\dots,p-1。

又因为 [x^{p-1}]f(x)=[x^{p-1}]g(x) 所以有 f(x)\equiv g(x)\pmod p。

令 x=p，即可得 (p-1)!\equiv p^{p-1}+1\pmod p，即 (p-1)!+1\equiv 0\pmod p。

逆定理证明：

反证法。若 (p-1)!+1\equiv 0\pmod p 且 p 不是质数，则 p 存在真质因子，取 p 任意真质因子 q。

由于 q\in[2,p-1]，所以 q|(p-1)!。

又因为 (p-1)!+1\equiv 0\pmod p 得到 p|((p-1)!+1)。

Theorem.4 中国剩余定理

\left\{ \begin{matrix} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \vdots\\ x\equiv a_n\pmod {m_n}\\ \end{matrix} \right.\\ M=\prod_{i=1}^n m_i ,M_i=\frac{M}{m_i},t_i\equiv M_i^{-1}\pmod {m_i}\\ x=(\sum_{i=1}^n a_it_iM_i)\bmod M

不会证明。考虑构造法。注意 m_1,m_2,\dots m_n 两两互质。

对于 a_i，t_iM_i\equiv 1\pmod {m_i} 保留了 a_i。

同时对于 j\ne i,t_jM_j\equiv 0\pmod {m_i} 去除了其它 a_j。（即 m_i|t_jM_j）

此外还可以证明 x 是模 M 意义下的唯一解。