代数基础
模 \(n\) 同余与可逆剩余类
1.1 同余与商群
设 \(n \in \mathbb{N}_1\)，\(a,b \in \mathbb{Z}\)。若
则称 \(a\) 与 \(b\) 模 \(n\) 同余，记作
模 \(n\) 的所有同余类构成商群
其中
在不引起歧义时，常把 \(\mathbb{Z}_n\) 简记为
1.2 可逆剩余类群
在 \(\mathbb{Z}_n\) 中定义乘法：
于是 \((\mathbb{Z}_n,\cdot)\) 是一个幺半群。它的所有可逆元素构成一个群，记为
由裴蜀定理可得：
因此
其中欧拉函数 \(\varphi(n)\) 表示不超过 \(n\) 且与 \(n\) 互质的正整数个数，定义为
特别地，若 \(p\) 是素数，则
且
初等数论三定理
2.1 有限群中的基本引理
设 \((G,\cdot)\) 是有限群。对任意 \(a\in G\)，都有
理由：由拉格朗日定理，元素 \(a\) 的阶 \(|a|\) 整除 \(|G|\)，所以
这个引理是费马小定理和欧拉定理的群论来源。
2.2 费马小定理
设 \(p\) 是素数，且 \(p\nmid a\)。则
两边同乘 \(a\)，也得到
证明思路：
因为 \(p\nmid a\)，所以 \(a\) 在 \(\mathbb{Z}_p^\times\) 中可逆。又
由有限群引理，
2.3 欧拉定理
设 \(n\in \mathbb{N}_2\)，且 \(\gcd(a,n)=1\)。则
证明思路：
由 \(\gcd(a,n)=1\) 可知 \(a\in \mathbb{Z}_n^\times\)，而
由有限群引理，
当 \(n=p\) 为素数时，\(\varphi(p)=p-1\)，欧拉定理退化为费马小定理。
欧拉函数的性质
定理表述
设 \(n\in \mathbb{N}_1\)。则
这里的求和是对 \(n\) 的所有正因子 \(d\) 求和。
证明思路
从恒等式
出发。
对每个 \(a\in \{1,\cdots,n\}\)，考虑
这个 \(d\) 一定是 \(n\) 的正因子。于是可以按照最大公因数的取值分组：
若 \(\gcd(a,n)=d\)，令
则
且
因此满足 \(\gcd(a,n)=d\) 的 \(a\) 的个数等于
所以
当 \(d\) 遍历 \(n\) 的正因子时，\(\frac nd\) 也遍历 \(n\) 的正因子。于是
例子
取 \(n=12\)。它的正因子为
于是
这正好验证了
2.4 威尔逊定理
设 \(p\) 是奇素数。则
证明思路：
在群 \(\mathbb{Z}_p^\times\) 中，每个元素都有逆元。若某个元素等于自己的逆元，则
因为 \(p\) 是素数，所以
也就是说，在 \(\mathbb{Z}_p^\times=\{1,2,\cdots,p-1\}\) 中，只有 \(1\) 和 \(p-1\) 是自己的逆元。
其余元素可以两两配对，每一对的乘积都是 \(1\)。因此
中国剩余定理
3.1 环中模理想的同余
设 \(R\) 是交换环，\(I\triangleleft R\) 是理想。若 \(a,b\in R\) 且
则称 \(a\) 与 \(b\) 模 \(I\) 同余，记作
等价地，
同余关系与加法、乘法、幂运算相容：若
则
3.2 中国剩余定理：理想版本
设 \(R\) 是交换环，\(I_1,\cdots,I_n\) 是一族两两互素的理想，即对任意 \(i\ne j\)，
则对任意 \(a_1,\cdots,a_n\in R\)，存在 \(x\in R\)，使得
证明构造：
只需构造一组元素 \(x_i\in R\)，使得
并且当 \(j\ne i\) 时，
于是
就是同余方程组的一个解。
以 \(i=1\) 为例。因为 \(I_1+I_j=R\)，对每个 \(j\ne 1\)，可以取
使得
令
则对 \(j\ne 1\)，由于 \(c_j\in I_j\)，有
另一方面，
展开后每一项都含有某个 \(b_j\in I_1\)，所以
因此
其余 \(x_i\) 同理构造。
3.3 中国剩余定理：同态版本
在上述条件下，映射
定义为
是满同态。
它的核为
由环同态第一定理，
特别地，若
则
3.4 整数版本
取 \(R=\mathbb{Z}\)，\(I_i=m_i\mathbb{Z}\)。若 \(m_1,\cdots,m_n\) 两两互素，则理想 \(m_i\mathbb{Z}\) 两两互素。
因此对任意整数 \(a_1,\cdots,a_n\)，同余方程组
有解。
并且解在模
意义下唯一，即所有解构成一个模 \(M\) 的同余类。
等价地，
这里求逆元的话：
当 p 为素数且 \(\gcd(a, p)=1\) 时，由费马小定理有：
两边同时乘以 \(a^{-1}\)（即 a 的逆元），得到：
因此，a 在模 p 下的逆元就是 \(a^{p-2} \bmod p\)。
实际计算时，通常使用快速幂（快速幂取模）来高效求出 \(a^{p-2} \bmod p\)。
这种方法只适用于 p 为素数的情况，而扩展欧几里得算法则适用于任意模数（只要互素）。
具体做法是：用扩展欧几里得算法求解方程 \(a x + p y = 1\)，得到的 x 就是 a 模 p 的一个逆元（通常再取模 p 化为最小正整数）。
3.5 具体求解过程
考虑同余方程组
其中 \(m_1,\cdots,m_n\) 两两互素。
第一步，令
第二步，对每个 \(i\)，令
因为 \(m_i\) 与其他模数都互素，所以
因此 \(M_i\) 在模 \(m_i\) 意义下有逆元。取 \(N_i\) 满足
第三步，构造
则原方程组的所有解为
原因是：对固定的 \(i\)，当 \(j\ne i\) 时，\(M_j\) 含有因子 \(m_i\)，所以
而 \(M_iN_i\equiv 1\pmod {m_i}\)，所以
这就说明 \(x_0\) 同时满足所有同余条件。
3.6 例子
求解同余方程组
这里 \(3,5,7\) 两两互素。令
分别计算
接着找逆元。
对模 \(3\)：
而
所以
对模 \(5\)：
所以
对模 \(7\)：
所以
于是
即
因为 \(233\equiv 23\pmod {105}\)，所以
检验：
因此原方程组的解为
小结
以上这几条结论之间的关系可以概括为：
- \(\mathbb{Z}_n^\times\) 是模 \(n\) 的可逆剩余类群，阶为 \(\varphi(n)\)。
- 有限群中任意元素满足 \(a^{|G|}=e\)，代入 \(\mathbb{Z}_p^\times\) 得到费马小定理，代入 \(\mathbb{Z}_n^\times\) 得到欧拉定理。
- 欧拉函数恒等式 \(n=\sum_{d\mid n}\varphi(d)\) 来自按 \(\gcd(a,n)\) 对 \(1,\cdots,n\) 分组。
- 威尔逊定理利用 \(\mathbb{Z}_p^\times\) 中逆元配对，只留下 \(1\) 和 \(-1\)。
- 中国剩余定理说明：两两互素的模数或理想，可以把多个同余条件合并为一个整体解。
同余的基本性质
本节我们介绍数论中一个重要的概念：同余，以及它的一些基本性质。
定义 给定一个正整数 \(m\) ，如果用 \(m\) 去除任意两个正整数 a 与 b 所得到的余数相同，我们就称 a,b 对模 m 同余，记为 \(a \equiv b \pmod{m}\) ，否则称 a,b 对模 \(m\) 不同余，记为 \(a \not\equiv b \pmod{m}\) ，其中 \(m\) 称作模。
基本性质
由同余的定义，它显然满足以下性质：
自反性： \(a \equiv a \pmod{m}\)。 对称性： 若 \(a \equiv b \pmod{m}\)，则 \(b \equiv a \pmod{m}\)。 传递性： 若 \(a \equiv b \pmod{m}\)，\(b \equiv c \pmod{m}\)，则 \(a \equiv c \pmod{m}\)。
此外由定义不难得到
定理1 整数 a,b 对模 m 同余的充要条件是 \(m \mid (a-b)\)。
证明
设 \(a=mq_1+r_1, b=mq_2+r_2, 0 \le r_1 < m, 0 \le r_2 < m\)。若 \(a \equiv b \pmod{m}\)，则 \(r_1=r_2\)，因此 \(a-b=m(q_1-q_2)\)，故 \(m \mid (a-b)\)。
反之，若 \(m \mid (a-b)\)，则 \(m \mid (m(q_1-q_2)+r_1-r_2)\)，所以 \(m \mid (r_1-r_2)\)，而 \(|r_1-r_2| < m\)，故 \(r_1=r_2\)。
定理1叙述的条件也可以作为同余的等价定义。
运算规则
由此定义及整除的性质，我们不难得到同余的一些性质。这些性质中有些与等式相同，模数发生变化的则不同。
- 若 \(a_1 \equiv b_1 \pmod{m}\)，\(a_2 \equiv b_2 \pmod{m}\)，则 \(a_1+a_2 \equiv b_1+b_2 \pmod{m}\)。
- 若 \(a_1 \equiv b_1 \pmod{m}\)，\(a_2 \equiv b_2 \pmod{m}\)，则 \(a_1a_2 \equiv b_1b_2 \pmod{m}\)。特别地，若 \(a \equiv b \pmod{m}\)，则 \(ka \equiv kb \pmod{m}\)。
翻译成计算机语言：
(a+b)%p = (a%p + b%p)%p(a*b)%p = (a%p * b%p)%p，推论：pow(a,b)%p = pow(a%p,b)%p- 若 \(a \equiv b \pmod{m}\)，如果 \(\gcd(d,m)=1\)，则 \(\frac{a}{d} \equiv \frac{b}{d} \pmod{m}\)。（这里前提是 \(d \mid a\) 并且 \(d \mid b\)）
证明 由定理1，\(m \mid (a-b)\)，又 \(\gcd(m,d)=1\)，故 \(m \mid \frac{a-b}{d} = \frac{a}{d} - \frac{b}{d}\)，所以 \(\frac{a}{d} \equiv \frac{b}{d} \pmod{m}\)。
- 如果 \(ac \equiv bd \pmod{m}\)，\(c \equiv d \pmod{m}\)，如果 \(\gcd(c,m)=1\)，则 \(a \equiv b \pmod{m}\)。
模运算满足结合律、交换律、分配律，具体如下：
A. 结合律
((a+b)%p+c)%p=(a+(b+c)%p)%p
((a*b)%p * c)%p= (a * (b*c)%p)%p
B. 交换律
(a+b)%p=(b+a)%p
(a*b)%p=(b*a)%p
C. 分配律
(a+b)%p=(a%p+b%p)%p
((a+b)%p*c)%p = ((a*c)%p + (b*c)%p)%p
重要定理
- 若 \(a \equiv b \pmod{m}\)，则 \(ka \equiv kb \pmod{km}\)。
- 若 \(a \equiv b \pmod{m}\)，d 为 \(a,b,m\) 的公因数，则 \(ad \equiv bd \pmod{md}\)。
- 若 \(a \equiv b \pmod{m_i}\)，\(i=1,2,\cdots,k\)，则 \(a \equiv b \pmod{\operatorname{lcm}(m_1,m_2,\cdots,m_k)}\)。（
lcm: 最小公倍数） - 若 \(a \equiv b \pmod{m}\)，\(d \mid m, d>0\)，则 \(a \equiv b \pmod{d}\)。
- 若 \(a \equiv b \pmod{m}\)，则 \(\gcd(a,m)=\gcd(b,m)\)。
简单应用
下面给出同余的一个简单应用：
定理2 一整数能被 3（或 9）整除的充要条件是它在十进制下各位数码的和能被 3（或 9）整除。
证明 显然只需要讨论正整数的情况。
设任一正整数 \(a=a_n 10^n + a_{n-1} 10^{n-1} + \cdots + a_0\)，\(0 \le a_i < 10\)，\(i=1,2,\cdots,n\)。由 \(10 \equiv 1 \pmod{3}\) 知 \(a \equiv a_n + a_{n-1} + \cdots + a_0 \pmod{3}\)，因此 \(3 \mid a\) 当且仅当 \(3 \mid \sum_{i=0}^n a_i\)。同理有 \(9 \mid a\) 当且仅当 \(9 \mid \sum_{i=0}^n a_i\)。
定理3 设正整数 \(a=a_n 1000^n + a_{n-1} 1000^{n-1} + \cdots + a_0\)，其中 \(0 \le a_i < 1000\)，\(i=0,1,\cdots,n\)，则 7（或 11,13）整除 a 的充要条件是 7（或 11,13）整除 \(\sum_{i=0}^n (-1)^i a_i\)。
证明 注意 \(1001=7 \times 11 \times 13\)，所以 1000 与 -1 模 7,11,13 同余。下面只讨论模 7 的情况，剩余两种情况同理。
由 \(1000 \equiv -1 \pmod{7}\) 知 \(a_i 1000^i \equiv a_i (-1)^i \pmod{7}\)，故 \(a \equiv \sum_{i=0}^n (-1)^i a_i \pmod{7}\)，
因此 \(7 \mid a\) 当且仅当 \(7 \mid \sum_{i=0}^n (-1)^i a_i\)。
我们来看几个例子：
例1 \(a=5874192\)，\(\sum_{i=0}^n a_i=5+8+7+4+1+9+2=36\) 能被 3、9 整除，故 5874192 能被 3、9 整除。
例2 \(a=75312289=75\times 1000^2+312\times 1000+289\)，\(\sum_{i=0}^n (-1)^i a_i=-75+312-289=-52\) 能被 13 整除，而不能被 7、11 整除。所以 13 是 a 的因数，7、11 不是 a 的因数。
大数求余解法
这里以求解 \(3^a \bmod (10^9+7)\) 为例（\(1 \le a \le 10000\)）。
大数越界： 当 a 增大时，最后返回的 \(3^a\) 大小以指数级别增长，可能超出 int32 甚至 int64 的取值范围，导致返回值错误。（int32 最多只有 \(3^{19}\)）
大数求余问题： 在仅使用 int32 类型存储的前提下，正确计算 \(x^a \bmod p\) 的值。
解决方案： 循环求余、快速幂求余，其中后者的时间复杂度更低，两种方法均基于以下求余运算规则推出：
即：乘积的余数等于余数的乘积再取余。
循环求余
根据求余运算性质推出（本题中 \(x<p\)，故 \(x\bmod p=x\)）：
解析： 利用此公式，可通过循环操作依次求 \(x^1, x^2, \cdots, x^{a-1}, x^a\) 对 p 的余数，保证每轮中间值 rem 都在 int32 取值范围中。封装方法代码如下所示。
## 求 (x^a) % p —— 循环求余法
def remainder(x, a, p):
rem = 1
for _ in range(a):
rem = (rem * x) % p
return rem- 时间复杂度 \(O(N)\)：其中 \(N=a\)，即循环的线性复杂度。
快速幂求余
根据求余运算性质可推出：
- 当 a 为奇数时 \(a/2\) 不是整数，因此分为以下两种情况（
//代表向下取整的除法）：
解析： 利用以上公式，可通过循环操作每次把指数 a 问题降低至指数 a//2 问题，只需循环 \(\log_2(N)\) 次，因此可将复杂度降低至对数级别。封装方法代码如下所示。
## 求 (x^a) % p —— 快速幂求余
def remainder(x, a, p):
rem = 1
while a > 0:
if a % 2:
rem = (rem * x) % p
x = x ** 2 % p
a //= 2
return rem帮助理解： 这里 rem 记录每次 a 为奇数时多出来的因子 x，最后会将 \(rem \times (x^a \bmod p)\) 化为 \(rem \times (x^0 \bmod p) = rem \times 1\) 的形式，即 rem 为余数答案。
参考资料
- 代数 Algebra [2 ed.] (Michael Artin) 翻译版: 代数 原书第2版第二版 麻省理工学院 Michael Artin 华章数学译丛 机械工业出版社
- Serge Lang, Algebra (经典, 推荐, 900页左右)
- 抽象代数2讲义.pdf
- Abstract Algebra I: Introduction to Group Theory;
Algebra II
Algebra III - 初等数论笔记整理
- 同余理论(Modulo)
- 伽罗瓦理论基本定理——群论和域论之间的一座桥梁
- https://kconrad.math.uconn.edu/blurbs/
- David S. Dummit, Richard M. Foote, Abstract Algebra Third Edition(经典, 900页左右)
- Thomas W. Hungerford, Algebra(经典, 推荐, 500页左右)
- Course Notes - J.S. Milne Top
- Visual Algebra textbook & supplemental materials
- GTM030 抽象代数讲义中文版（GitHub）
- 中科大近世代数讲义（PDF）
- 张浩哲抽象代数讲义（PDF）
- 黎永锦抽象代数讲义（Archive.org