信息安全数学基础

Chapter 1. 课程须知

前几天在社交媒体上读到了这样的一个片段，家长在提问一个在上小学的孩子，说：

“3+9*8 等于多少？”

小孩子迟疑了，支支吾吾不敢作答。孩子知道要“先乘除后加减”，但是对后面的“9*8”，却说老师没有教过：

“八九七十二，九八……，我不知道……”

家长似乎有些失去耐心了：

“8 乘以 9，和 9 乘以 8 是一样的！八九七十二，9 乘以 8，也就是 72，再加三就是 75 了。”

其实在很多时候，我们会下意识地认为，“整数乘法满足乘法交换律”是一个很简单、甚至不需要学就能弄懂的公理。

但在小孩子眼中，并非如此。

孩子会觉得 9*8 是一个老师还没有教过的新知识，它与乘法口诀表的八九七十二是不同的。

小孩子的直觉是对的。

当我们在线性代数中，学习了矩阵乘法时，我们又一次感受到乘法交换律应用的局限性——原来并不是世间万物都满足“交换律”。那么在数学中，什么样的乘法可以使用交换律，或者再想一想，结合律和分配律的应用又是怎样的呢？

没错，这一次，我们将从整数理论出发，了解数论中“群”“环”“域”的概念，它也是许多密码算法原理所需要的数学基础。

进一步地，我们还将一起探索密码学原理和许多具体的算法，比如椭圆曲线、平方乘算法、素性检测、因子分解算法、离散对数问题等等，它们是理解密码学中许多问题所必需的数学知识。

由于这份笔记是我自己撰写的，对知识的理解、对问题的解答难免有所疏漏、甚至错误。如果您在阅读的过程中发现任何问题，欢迎与我联系：2053182@tongji.edu.cn，请您一并注明所在单位（或学院）和姓名，我会在收到邮件后的第一时间与您联系。

最后——

“那就一起头也不回地向着光亮走下去吧”

欢迎来到信息安全这一方小小天地，愿我的点滴文字，能与你一同进步。

同济大学电子与信息工程学院 ChestnutSilver / 王润霖

2023 年 8 月 21 日

Chapter 2. 密码学数学基础引论

Chapter 3. 抽象代数基本概念

1. 元素集合与运算

在这一节，我们将接触群、环、域的最基本的概念（也就是定义），并会认识一个特殊的群——阿贝尔群。我们会对数学运算中加法和乘法的交换律、结合律与分配律，数学运算的封闭性，以及单位元、逆元有一个比较系统的审视。

在学习这一节的过程中，我们将会定义许多运算，这些运算通常用运算符（ +、 · ）等表示。

注意！不要把这些下意识地想象成整数加法和乘法，而要注意对运算符的具体定义。

我们还会定义执行运算的元素集合，在整数加法中，元素集合是所有整数；但在我们的定义中，元素集合可能是所有奇数、所有偶数、R 上的所有 n*n 矩阵、R 上的所有 n*n 可逆矩阵……可能的定义有很多很多，不要直接想象成全体整数。

也许，学完这一节后，你会对数学运算有一个新的理解。这节内容与高等代数部分章节有些相似，如果没有接触过高代也没关系。

2. 群

2.1 群的概念

群（Group）(G, ∙ )，其中 G 为元素集合， ∙ 是定义在 G 上的二元运算，满足下面的四个性质：

性质	含义
封闭性	对 \(\forall a,b\in G\)，有 \(a\cdot b\in G\)
结合律	对 \(\forall a,b,c\in G\)，有 \((a\cdot b)\cdot c=a\cdot(b\cdot c)\)
存在单位元	\(\exists e\in G\)，使得对于 \(\forall a\in G\)，有 \(e\cdot a=a\cdot e=a\)，称 \(e\) 为 \(G\) 的单位元
可逆性	对 \(\forall a\in G\)，\(\exists b\in G\) 满足 \(a\cdot b=b\cdot a=e\)，其中 \(b\) 称为 \(a\) 的逆元，表示成 \(b=a^{-1}\)

注：

单位元通常用 \(e\)、1 或 0 表示。
证明一个代数系统是群，可以通过逐一验证每一个性质。
简写：为了简约起见，在运算符 · 明确的情况下，群 (G, · ) 经常用 G 来代替。

如何理解群的四个性质？

文字描述进一步理解

封闭性：群内任意两个元素或两个以上的元素（相同的或不同的）的结合（积）都是该集合的一个元素。即：假设对于群 G 操作（运算）是*，对于 G 里的任意元素 \(a,b\)，那么 \(a*b\) 和 \(b*a\) 都必须是 G 的元素。
结合律：虽然群元素不一定要求满足交换律，但必须满足结合律，即对 G 中任意元素 \(a,b,c\) 都有 \((a*b)*c=a*(b*c)\)。
存在单位元：集合 G 内存在一个单位元素 \(e\)，它和集合中任何一个元素的积都等于该元素本身，即对于 G 中每个元素 \(a\) 都有 \(e*a=a*e=a\)。
可逆性：对 G 中每个元素 \(a\)，在 G 中都有元素 \(a^{-1}\)，使 \(a^{-1}*a=a*a^{-1}=e\)。

群的性质：群有很多性质，例如“群满足消去律”“单位元 \(e\) 是唯一幂等元”“群同态保持单位元/逆元”等，这些性质后面会详细介绍。
群的判定：目前，我们使用了“逐一验证每一个性质”的方法判定一个代数系统是否为群；与此同时，还有其他更为简便的方法，例如使用同态、逆元、线性方程、消去律等进行群的判定，这些方法仍然在后面介绍。

下面，我们来通过一个具体的元素集合和二元运算实例，加深一下对群的概念和四个性质的理解。

练习 1.

题目思路解答

设 A 是所有奇数构成的集合，B 是所有偶数构成的集合，请问 A、B 关于整数的加法运算是否是群？请证明你的结论。

在这道题目里面，我们要做两件事。第一，判断所有奇数构成的集合关于整数的加法运算是否是群；第二，判断所有偶数构成的集合关于整数的加法运算是否是群。你瞧，题目已经定义好了元素集合和二元运算；下面，我们只需要逐一验证群的四个性质，就可以判断它们分别是否是群了。

技巧：如何规范地验证群的性质呢？例如：我们都知道，奇数与奇数的和是偶数，它说明了“奇数加法不满足封闭性”，但是，如何将这句话用规范的数学语言描述呢？

在高中时，我们经常使用 \(2n+1\ (n\in \Bbb Z)\) 的方法来表示一个奇数，在验证群的性质时，我们也常用这种方法进行数学描述。我们假设题目中的集合 A 中有两个元素 \(a,b\)（它们是集合中任意的两个元素），这样，我们就可以用 \(a=2n+1,\ b=2m+1\ (n,m\in \Bbb Z)\)，来表示 \(a\) 和 \(b\) 了；进一步地，\(a+b=2n+1+2m+1=2(n+m+1)\notin A\)，它规范地使用了数学语言，描述了“奇数加法不满足封闭性”的证明过程。

其他性质的验证也与此同理。

这种数学语言在验证群的性质中是常见的。

此外，在验证“存在单位元”性质时，我们要找到这个单位元；在验证“可逆性”性质时，我们要对一个一般的集合元素找到它的逆元，从而说明集合中的每一个元素都有逆元。

A 关于整数的加法运算不是群；B 关于整数的加法运算是群。

证明：

（1）对于 \(\forall a,b\in A\)，设 \(a=2n+1,\ b=2m+1\ (n,m\in \Bbb Z)\)

则：\(a+b=2n+1+2m+1=2(n+m+1)\notin A\)

不满足封闭性，因此 A 关于整数的加法运算不是群。

（2）对于 \(\forall a,b,c\in B\)，设 \(a=2p,\ b=2q,\ c=2r\ (p,q,r\in \Bbb Z)\)

则：①\(a+b=2p+2q=2(p+q)\in B\)，满足封闭性；

②\((a+b)+c=(2p+2q)+2r=2p+2q+2r=2p+(2q+2r)=a+(b+c)\)，满足结合律；

③\(\exists e=0,\ e\in B,\ 0+2p=2p+0=2p\)，0 为 B 的单位元，满足存在单位元；

④\(\forall a\in B,\ a=2p,\ \exists(-2p)\in B\) 满足 \(2p+(-2p)=(-2p)+2p=0\)，此时 \(-2p\) 为 \(2p\) 的逆元，满足可逆性。

满足群的四个性质，因此 B 关于整数的加法运算是群。

证毕。

2.2 阿贝尔群的概念

若群 G 满足交换性则称为阿贝尔群（Abelian 群），或者交换群。

首先，这个代数系统需要是一个群（需要满足群的四个性质），此外，如果它还满足交换律，那么它称为阿贝尔群。

性质	含义
交换律	对 \(\forall a,b\in G\)，有 \(a\cdot b=b\cdot a\)

证明一个代数系统是阿贝尔群，也可以通过逐一验证每一个性质。

2.3 群、阿贝尔群的例子

\((\Bbb Z, + )\)：是阿贝尔群。\(\Bbb Z\) 表示整数集合 \(\Bbb Z=\{…,-2,-1,0,1,2,…\}\)，\(+\) 表示定义在其上的加法运算。
\((\Bbb Z_{n}, + )\)：是阿贝尔群。\(\Bbb Z_{n}\) 表示比 \(n\) 小的非负整数集合（例：\(\Bbb Z_{4}=\{0,1,2,3\}\)），\(+\) 表示 \(mod\ n\) 加法运算，即：\(a+b\) 表示 \((a+b) mod\ n\)，注意这里是在 \(\Bbb Z\) 上的 \(+\) 运算。
\((\Bbb Z^{*}_{n}, · )\)：是阿贝尔群。\(\Bbb Z^{*}_{n}=\{x\in \Bbb Z_{n} \mid x 与 n 互素\}\)（例：\(n=3,\Bbb Z^{*}_{3}=\{1,2\}\)；\(n=4,\Bbb Z^{*}_{4}=\{1,3\}\)），\(·\) 表示 \(mod\ n\) 乘法运算，即：\(a·b=(ab) mod\ n\)。
\(Mat_{n}(\Bbb R)\) 关于矩阵加法运算：是阿贝尔群。\(Mat_{n}(\Bbb R)\) 表示 \(\Bbb R\) 上的所有 \(n\times n\) 矩阵的集合；单位元是全 0 矩阵 \(0_{n\times n}\)。
\(GL(n,\Bbb R)\) 关于矩阵乘法运算：是群，但不是阿贝尔群。\(GL(n,\Bbb R)\) 表示 \(\Bbb R\) 上所有 \(n\times n\) 可逆矩阵的集合；单位元是单位矩阵 \(I_{n\times n}\)；它是一个一般线性群。
\(S_{n}\) 关于映射合成运算：是群。设 \(X\) 是大小为 \(n\) 的有限集合，记 \(S_{n}=\{集合 X 上的所有置换\}\)。其中：\(S_{1}\)，\(S_{2}\) 是阿贝尔群，\(S_{3}\) 不是阿贝尔群，当 \(n>3\) 时，\(S_{n}\) 不是阿贝尔群。

如何理解映射合成运算？

定义举例

映射合成运算：设 \(f:A\rightarrow B,\ g:B\rightarrow C\) 为两个映射，称 \((g·f)(a):=g(f(a)),\forall a\in A\) 为映射 \(g\) 与 \(f\) 的乘积或合成。

映射合成运算满足结合律，但 \(n\geq 3\) 时不满足交换律。

\(h·(g·f)=(h·g)·f\).

\(X\) 是大小为 \(n\) 的有限集合，最简单的例子：\(X=\{1,2,…,n\}\).

（1）置换的例子：

设 \(X=\{1,2,3\}\)，此时 \(S_{3}\) 中的一个元素 \(\begin{pmatrix} 1,2,3 \\ 2,1,3 \end{pmatrix}\in S_{3}\)，记这个元素为 \(e\)，它表示的置换是：\(e(1)=2,\quad e(2)=1,\quad e(3)=3\).

（2）\(S_{n}\) 的例子：

\(S_{n}=\{x上的所有置换\}\)，我们以 \(n=3\) 为例：

\(S_{3}=\left\{ \begin{pmatrix} 1,2,3 \\ 1,2,3 \end{pmatrix}, \begin{pmatrix} 1,2,3 \\ 2,1,3 \end{pmatrix}, \begin{pmatrix} 1,2,3 \\ 1,3,2 \end{pmatrix}, \begin{pmatrix} 1,2,3 \\ 3,2,1 \end{pmatrix}, \begin{pmatrix} 1,2,3 \\ 2,3,1 \end{pmatrix}, \begin{pmatrix} 1,2,3 \\ 3,1,2 \end{pmatrix} \right\}\)

（3）映射合成运算的例子：

注意映射合成在计算时从右向左计算，\((g·f)(a):=g(f(a))\)，例如：

\(\begin{pmatrix} \color{red}{1}\color{black},\color{green}{2}\color{black},\color{blue}{3} \\ \color{red}{2}\color{black},\color{green}{1}\color{black},\color{blue}{3} \end{pmatrix}\begin{pmatrix} \color{red}{1}\color{black},\color{blue}{2}\color{black},\color{green}{3} \\ \color{red}{1}\color{black},\color{blue}{3}\color{black},\color{green}{2} \end{pmatrix}=\begin{pmatrix} \color{red}{1}\color{black},\color{blue}{2}\color{black},\color{green}{3} \\ \color{red}{2}\color{black},\color{blue}{3}\color{black},\color{green}{1} \end{pmatrix}\)

上述群、阿贝尔群各例的证明过程（简略）？

\((\Bbb Z, + )\)\((\Bbb Z_{n}, + )\)\((\Bbb Z^{*}_{n}, · )\)\(Mat_{n}(\Bbb R)\) 关于矩阵加法运算\(GL(n,\Bbb R)\) 关于矩阵乘法运算\(S_{n}\) 关于映射合成运算

封闭性：对 \(\forall a,b\in \Bbb Z\)，有 \(a+b\in \Bbb Z\)；
结合律：对 \(\forall a,b,c\in \Bbb Z\)，有 \((a+b)+c=a+(b+c)\)；
0是单位元：对 \(\forall a\in \Bbb Z\)，有 \(0+a=a+0=a\)；
可逆性：对 \(\forall a\in \Bbb Z\)，有 \((-a)+a=a+(-a)=0\)，因此 \(-a\) 是 \(a\) 的逆元；
交换律：对 \(\forall a,b\in \Bbb Z\)，有 \(a+b=b+a\)。

介绍同余性质时再证明。

封闭性：设 \(A,B\in Mat_{n}(\Bbb R)\)，则 \(A,B\) 是 \(n\times n\) 矩阵，于是 \(A+B\) 也是 \(n\times n\) 矩阵，从而 \(A+B\in Mat_{n}(\Bbb R)\).
结合律：因为矩阵的加法满足结合律，所以 \(Mat_{n}(\Bbb R)\) 中的加法运算也满足结合律。
全 0 矩阵是单位元：全 0 矩阵 \(0_{n\times n}\in Mat_{n}(\Bbb R)\)，且对任意的矩阵 \(A\in Mat_{n}(\Bbb R)\)，有：\(0_{n\times n}+A=A+0_{n\times n}=A\)，所以全 0 矩阵 \(0_{n\times n}\) 是 \(Mat_{n}(\Bbb R)\) 的单位元。
可逆性：对于 \(\forall A\in Mat_{n}(\Bbb R)\)，\(A\) 是 \(n\times n\) 矩阵，于是 \(-A\) 存在且是 \(n\times n\) 矩阵，从而 \(-A\in Mat_{n}(\Bbb R)\)，且：\(A+(-A)=(-A)+A=0_{n\times n}\)，所以 \(Mat_{n}(\Bbb R)\) 中的每个元素在 \(Mat_{n}(\Bbb R)\) 中都可逆。
交换律：因为矩阵的加法满足交换律，所以 \(Mat_{n}(\Bbb R)\) 中的加法运算也满足交换律。

封闭性：设 \(A,B\in GL(n,\Bbb R)\)，则 \(A,B\) 可逆，于是 \(AB\) 也可逆，从而 \(AB\in GL(n,\Bbb R)\).
结合律：因为矩阵的乘法满足结合律，所以 \(GL(n,\Bbb R)\) 中的乘法运算也满足结合律。
单位矩阵是单位元：单位矩阵 \(E\in GL(n,\Bbb R)\)，且对任意的矩阵 \(A\in GL(n,\Bbb R)\)，有：\(EA=AE=A\)，所以单位矩阵 \(E\) 是 \(GL(n,\Bbb R)\) 的单位元。
可逆性：对于 \(\forall A\in GL(n,\Bbb R)\)，\(A\) 可逆，于是 \(A^{-1}\) 存在且可逆，从而 \(A^{-1}\in GL(n,\Bbb R)\)，且：\(A\cdot A^{-1}=A^{-1}\cdot A=E\)，所以 \(GL(n,\Bbb R)\) 中的每个元素在 \(GL(n,\Bbb R)\) 中都可逆。

注：相似题目，见“练习3”.

\(S_{1},S_{2}\)是阿贝尔群，由于它们的形式简单，因此是容易证得的。

当 \(n\geq 3\) 时，证明过程见“练习2”。

如何证明一个代数系统不是阿贝尔群？（以 \(S_{3}\) 为例）

我们一般通过对某个性质举一个反例的方法，证明一个代数系统不是阿贝尔群。

以 \(S_{3}\) 为例，证明如下：

设 \(X=\{x_{1},x_{2},x_{3}\}\)，令 \(e,e'\in S_{3}\) 满足：

\(e(x_{1})=x_{1},\quad e(x_{2})=x_{3},\quad e(x_{3})=x_{2}\)，

\(e'(x_{1})=x_{2},\quad e'(x_{2})=x_{3},\quad e'(x_{3})=x_{1}\)，

那么：\(ee'(x_{1})=e(x_{2})=x_{3},\quad e'e(x_{1})=e'(x_{1})=x_{2}\).

因此：\(ee'\not=e'e\).

所以，\(S_{3}\) 不是阿贝尔群。

证毕。

练习 2.

题目思路解答

证明 \(n>3\) 时，\(S_{n}\) 不是阿贝尔群。

刚才我们已经提到，一般通过对某个性质举一个反例的方法，证明一个代数系统不是阿贝尔群，这个反例可以是很具体的。

我们已经证明过 \(S_{3}\) 不是阿贝尔群了，当 \(n>3\) 时，\(S_{n}\) 与 \(S_{3}\) 的区别，无非就是又多了几列映射，我们只需要让多出的这几列映射为对自身的映射，不去关注它（方便证明过程中的计算），从而只关注前 3 列的映射关系。

此时，再证明它不满足交换律，就和证明 \(S_{3}\) 不满足交换律一样简单了。

证明：

先证 \(n=3\) 时，\(S_{n}\) 不是阿贝尔群。

\(\begin{pmatrix} 1,2,3 \\ 1,3,2 \end{pmatrix},\begin{pmatrix} 1,2,3 \\ 2,1,3 \end{pmatrix}\in S_{3}\)

\(\begin{pmatrix} 1,2,3 \\ 1,3,2 \end{pmatrix}\begin{pmatrix} 1,2,3 \\ 2,1,3 \end{pmatrix}=\begin{pmatrix} 1,2,3 \\ 3,1,2 \end{pmatrix}\)

\(\begin{pmatrix} 1,2,3 \\ 2,1,3 \end{pmatrix}\begin{pmatrix} 1,2,3 \\ 1,3,2 \end{pmatrix}=\begin{pmatrix} 1,2,3 \\ 2,3,1 \end{pmatrix}\)

且：\(\begin{pmatrix} 1,2,3 \\ 3,1,2 \end{pmatrix}\not=\begin{pmatrix} 1,2,3 \\ 2,3,1 \end{pmatrix}\)，不满足交换律。

因此 \(S_{3}\) 不是阿贝尔群。

当 \(n>3\) 时，令满足 \(i>3\) 的所有第 \(i\) 列，均为对自身的映射。

即：\(\begin{pmatrix} 1,2,3,\ldots\ldots,n \\ 1,3,2,\underbrace{\ldots\ldots,n}_{对自身映射} \end{pmatrix},\begin{pmatrix} 1,2,3,\ldots\ldots,n \\ 2,1,3,\underbrace{\ldots\ldots,n}_{对自身映射} \end{pmatrix}\in S_{n}\)

\(\begin{pmatrix} 1,2,3,\ldots,n \\ 1,3,2,\ldots,n \end{pmatrix}\begin{pmatrix} 1,2,3,\ldots,n \\ 2,1,3,\ldots,n \end{pmatrix}=\begin{pmatrix} 1,2,3,\ldots,n \\ 3,1,2,\ldots,n \end{pmatrix}\)

\(\begin{pmatrix} 1,2,3,\ldots,n \\ 2,1,3,\ldots,n \end{pmatrix}\begin{pmatrix} 1,2,3,\ldots,n \\ 1,3,2,\ldots,n \end{pmatrix}=\begin{pmatrix} 1,2,3,\ldots,n \\ 2,3,1,\ldots,n \end{pmatrix}\)

且：\(\begin{pmatrix} 1,2,3,\ldots\ldots,n \\ 3,1,2,\underbrace{\ldots\ldots,n}_{对自身映射} \end{pmatrix}\not=\begin{pmatrix} 1,2,3,\ldots\ldots,n \\ 2,3,1,\underbrace{\ldots\ldots,n}_{对自身映射} \end{pmatrix}\) 不满足交换律。

因此 \(n>3\) 时，\(S_{n}\) 不是阿贝尔群。

证毕。

练习 3.

题目思路解答

假设 \(\mathscr A\) 是所有形如 \(A=\begin{bmatrix} a & b \\ 0 & 1 \\ \end{bmatrix}\) 的 \(2\times 2\) 矩阵构成的集合，其中 \(a\not=0\).对于实数上的矩阵乘法运算，(a)证明 \(\mathscr A\) 是群。(b)\(\mathscr A\) 是否是阿贝尔群？请证明你的结论。

看到这个形式，可以想到我们前面学到的：

\(GL(n,\Bbb R)\) 关于矩阵乘法运算：是群，但不是阿贝尔群。\(GL(n,\Bbb R)\) 表示 \(\Bbb R\) 上所有 \(n\times n\) 可逆矩阵的集合；单位元是单位矩阵 \(I_{n\times n}\)；它是一个一般线性群。

它要求集合中的元素是 \(n\times n\) 可逆矩阵，而这道题目中的元素是形如 \(A=\begin{bmatrix} a & b \\ 0 & 1 \\ \end{bmatrix}\) 的 \(2\times 2\) 矩阵。

回想一下线性代数的知识：我们可以用“行列式不等于零的矩阵可逆”的方法，计算行列式：\(\begin{vmatrix} a & b \\ 0 & 1 \\ \end{vmatrix}=a-0=a\)，又因为题目中说 \(a\not=0\)，所以它是一个 \(2\times 2\) 可逆矩阵的集合，根据前面学的结论，它是群，但不是阿贝尔群。

得到了结论，我们如何证明呢？

事实上，在证明 \(GL(n,\Bbb R)\) 的封闭、可逆等性质时，还可以充分利用“行列式不等于零的矩阵可逆”的性质，这样的思路是常见的。

（a）证明：

对于 \(\forall p,q,r\in \mathscr A\)，设 \(p=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix},q=\begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix},r=\begin{bmatrix} r_{1} & r_{2} \\ 0 & 1 \\ \end{bmatrix}\)，其中 \(p_{1},q_{1},r_{1}\not=0\).

① \(p\cdot q=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}=\begin{bmatrix} p_{1}q_{1} & p_{1}q_{2}+p_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(\because p_{1}q_{1}\not=0,\quad \begin{bmatrix} p_{1}q_{1} & p_{1}q_{2}+p_{2} \\ 0 & 1 \\ \end{bmatrix}\in \mathscr A\)

\(\therefore\) 满足封闭性。

② \((p\cdot q)\cdot r = \left(\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}\right)\cdot \begin{bmatrix} r_{1} & r_{2} \\ 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} p_{1}q_{1} & p_{1}q_{2}+p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} r_{1} & r_{2} \\ 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} p_{1}q_{1}r_{1} & p_{1}q_{1}r_{2}+p_{1}q_{2}+p_{2} \\ 0 & 1 \end{bmatrix}\)

\(p\cdot (q\cdot r) = \begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \left(\begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} r_{1} & r_{2} \\ 0 & 1 \\ \end{bmatrix}\right) = \begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} q_{1}r_{1} & q_{1}r_{2}+q_{2} \\ 0 & 1 \end{bmatrix}=\begin{bmatrix} p_{1}q_{1}r_{1} & p_{1}q_{1}r_{2}+p_{1}q_{2}+p_{2} \\ 0 & 1 \end{bmatrix}\)

\(\because (p\cdot q)\cdot r = p\cdot (q\cdot r)\)

\(\therefore\) 满足结合律。

③ \(\exists e\in \mathscr A,\quad e=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},\) 使得 \(\forall p\in\mathscr A\)，设 \(p=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(e\cdot p=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix},\quad p\cdot e=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(e\cdot p=p\cdot e=p\)

\(e\) 为 \(\mathscr A\) 的单位元。

\(\therefore\) 满足存在单位元。

④ 对于 \(\forall p\in\mathscr A\)，设 \(p=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(\exists p'\in\mathscr A,\quad p'=\begin{bmatrix} \frac{1}{p_{1}} & -\frac{p_{2}}{p_{1}} \\ 0 & 1 \end{bmatrix}\)，满足：

\(p\cdot p'=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} \frac{1}{p_{1}} & -\frac{p_{2}}{p_{1}} \\ 0 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}=e\)

\(p'\cdot p=\begin{bmatrix} \frac{1}{p_{1}} & -\frac{p_{2}}{p_{1}} \\ 0 & 1 \end{bmatrix}\cdot \begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}=\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}=e\)

\(p\cdot p'=p'\cdot p=e\)，\(p'\) 为 \(p\) 的逆元。

\(\therefore\) 满足可逆性。

综上，\(\mathscr A\) 是群。

（b）\(\mathscr A\) 不是阿贝尔群。

证明：

对于 \(\forall p,q\in\mathscr A\)，设 \(p=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix},q=\begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(p\cdot q=\begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}=\begin{bmatrix} p_{1}q_{1} & p_{1}q_{2}+p_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(q\cdot p=\begin{bmatrix} q_{1} & q_{2} \\ 0 & 1 \\ \end{bmatrix}\cdot \begin{bmatrix} p_{1} & p_{2} \\ 0 & 1 \\ \end{bmatrix}=\begin{bmatrix} p_{1}q_{1} & p_{2}q_{1}+q_{2} \\ 0 & 1 \\ \end{bmatrix}\)

\(\begin{bmatrix} p_{1}q_{1} & p_{1}q_{2}+p_{2} \\ 0 & 1 \\ \end{bmatrix}\not=\begin{bmatrix} p_{1}q_{1} & p_{2}q_{1}+q_{2} \\ 0 & 1 \\ \end{bmatrix}\)，（\(p_{1}q_{2}+p_{2}\not=p_{2}q_{1}+q_{2}\) 时）

\(\therefore p\cdot q\not=q\cdot p\)，（\(p_{1}q_{2}+p_{2}\not=p_{2}q_{1}+q_{2}\) 时）

\(\therefore\) 不满足交换律。

\(\mathscr A\) 不是阿贝尔群。

证毕。

3. 环和域

3.1 环和域的概念

下面我们来介绍“环”，它的性质比“群”要多许多，这类代数系统同时定义了 \(+\)、\(\cdot\) 两个二元运算。

环（Ring）\((\Bbb R,+,\cdot)\)：\(\Bbb R\) 是元素集合，\(+,\cdot\) 是定义在 \(\Bbb R\) 上的二元运算，且满足如下三类性质则称为环：

\((\Bbb R,+)\) 是阿贝尔群；
乘法 \(\cdot\) 满足：封闭性、结合律、存在单位元；
\(+,\cdot\) 满足：分配律。

在这里，我们将 \((\Bbb R,+)\) 的单位元记为 0，称为“加法单位元”；将 \((\Bbb R,\cdot)\) 的单位元记为 1，称为“乘法单位元”。

分配律的含义是：对 \(\forall a,b,c\in\Bbb R\)，有 \((a+b)c=(ac)+(bc),\quad c(a+b)=(ca)+(cb)\).

交换环： 在 \((\Bbb R,+,\cdot)\) 是一个环的基础上，如果还满足下面的一类性质，则称为交换环。

乘法 \(\cdot\) 满足：交换律。

域（Field）： 在 \((\Bbb R,+,\cdot)\) 是一个交换环的基础上，如果还满足下面的一类性质，则称为域。

\(0\not=1\)，所有非 0 元素都有乘法逆元。

其中，元素个数无限的称为无限域，个数有限的域称为有限域。

域还有另一种定义方法，它也是一个定理。

\((\Bbb F,+,\cdot)\) 是域，等价于下面的三个条件同时满足：

\((\Bbb F,+,0)\) 是阿贝尔群；
\((\Bbb F^{*},\cdot,1)\) 是阿贝尔群；（其中 \(F^{*}=F\backslash\{0\}\)）
\(+,\cdot\) 满足分配律。

3.2 环和域的例子

\((Mat_{n}(\Bbb R),+,\cdot)\) 是环，其中 \(+,\cdot\) 分别表示 \(\Bbb R\) 上的矩阵加法和乘法。在 \(n>1\) 时，它不是交换环。
\((\Bbb Z, +,\cdot)\) 是交换环，但不是域。原因：整数 \(\Bbb Z\) 是一个交换环，但是由于不符合“所有非 0 元素都有乘法逆元”（例如：\(2^{-1}=1/2,\quad 1/2\notin\Bbb Z)\)，所以它不是一个域。
\((\Bbb Z_{m}, +,\cdot)\) 是交换环，当且仅当 \(m\) 为素数时是域。在同余式部分会给出证明。
实数域 \((\Bbb R,+,\cdot)\)、有理数域 \((\Bbb Q,+,\cdot)\)、复数域 \((\Bbb C,+,\cdot)\) 都是域。

4. 抽象代数和数论

这一小节简要了解就可以了。

1.由数论问题发展出抽象代数。

Galois 证明了方程次数 \(\geq 5\) 时不存在根式求解公式。

2.数论问题为抽象代数提供具体的例子。

例如：

\((\Bbb Z_{n}, + )\)：是阿贝尔群。\(\Bbb Z_{n}\) 表示比 \(n\) 小的非负整数集合，\(+\) 表示 \(mod\ n\) 加法运算。

\((\Bbb Z^{*}_{n}, · )\)：是阿贝尔群。\(\Bbb Z^{*}_{n}=\{x\in \Bbb Z_{n} \mid x 与 n 互素\}\)，\(·\) 表示 \(mod\ n\) 乘法运算。当 \(n\) 是素数时，它是循环群。

\((\Bbb Z_{p}, +,\cdot)\) 是域。其中 \(p\) 为素数。

Chapter 4. 整数理论

在这一小节里面，我们将会学习整数理论，它包括很多与整数相关的定理和性质，需要我们在题目中灵活应用，也是后面章节的重要基础。

整数理论可以出的题目有很多，其中，大部分是证明题，会反复应用学到的定理和性质，有些题目很难在第一次遇见时就想到解题思路；没关系，只要我们把学到的这些题目的思路和方法都弄懂，在期末考试中也一定能发挥出优秀的水平。

这两个符号，我们一定都认识：

\(\Bbb Z\)：整数集合，\(\Bbb Z^{+}\)：正整数集合。

可以再顺带复习一下上一节中，\(\Bbb Z_{n}\)、\(\Bbb Z^{*}_{n}\)、\(Mat_{n}(\Bbb R)\)、\(GL(n,\Bbb R)\)、\(S_{n}\) 的含义。

1. 整除性

1.1 整除的定义

整除的定义：\(\forall a,b\in\Bbb Z\)，其中 \(b\not=0\)，如果 \(\exists q\in\Bbb Z\) 满足：\(a=bq\)，就说 \(b\) 整除 \(a\)，记作 \(b\mid a\)；\(b\) 叫做 \(a\) 的因数（或因子），\(a\) 叫做 \(b\) 的倍数。

如果符合上面条件的整数 \(q\) 不存在，则说 \(b\) 不整除 \(a\)，记作 \(b\nmid a\).

1.2 整除的基本性质

整除的定义很好理解，关键是整除性质的理解和使用。

我们先来看一下整除有哪些基本性质：

整除的基本性质

如果 \(c\mid b\)，\(b\mid a\)，则 \(c\mid a\).（传递性）
如果 \(b\mid a\)，则 \(cb\mid ca\).
如果 \(c\mid a,\ c\mid b\)，则对 \(\forall m,n\in\Bbb Z\)，有 \(c\mid ma+nb\).
如果 \(b\mid a\) 且 \(a\not=0\)，则 \(|b|\leq |a|\).
如果 \(cb\mid ca\)，\(c\not=0\)，则 \(b\mid a\).
如果 \(b\mid a\)，\(a\not=0\)，则 \(\frac{a}{b}\mid a\).
如果 \(c\mid a+b,\ c\mid a\)，则 \(c\mid b\).

由(2.)和(5.)可得：如果 \(c\not=0\)，则 \(b\mid a\Leftrightarrow cb\mid ca\).

利用整除的定义，很容易证明这些性质，证明过程简要了解就可以了。

如何证明整除的基本性质？

性质1性质2性质3性质4性质5性质6性质7

\(c\mid b\Rightarrow b=cq_{1}\)

\(b\mid a\Rightarrow a=bq_{2}\)

\(\therefore a=cq_{1}q_{2}\)

\(c\not=0\)

\(\therefore c\mid a\)

\(b\mid a\Rightarrow a=bq\Rightarrow ca=cbq\)

\(b\not=0,\ c\not=0\Rightarrow cb\not= 0\)

\(\therefore cb\mid ca\)

\(c\mid a\Rightarrow a=cq_{1}\)

\(c\mid b\Rightarrow b=cq_{2}\)

\(ma+nb=mcq_{1}+ncq_{2}=c(mq_{1}+nq_{2})\)

\(\therefore c\mid ma+nb\)

\(b\mid a\Rightarrow a=bq,\ b\not=0,\ q\in\Bbb Z\)

\(a\not=0,\ b\not=0,\ q\in\Bbb Z\Rightarrow q\not=0\Rightarrow |q|\geq 1\Rightarrow \cfrac{|a|}{|b|}\geq 1\)

\(\therefore |b|\leq |a|\)

\(cb\mid ca,\ c\not=0,\ b\not=0\Rightarrow ca=cbq,\ c\not=0,\ b\not=0\Rightarrow a=bq,\ b\not=0\)

\(\therefore b\mid a\)

\(b\mid a,\ a\not=0\Rightarrow a=bq\Rightarrow a=(\cfrac{a}{b})b,\ \cfrac{a}{b}\not=0,\ q=\cfrac{a}{b}\in\Bbb Z,\ b\in\Bbb Z\)

\(\therefore \cfrac{a}{b}\mid a\)

\(c\mid a+b,\ c\mid a\Rightarrow a+b=mc,\ a=nc\Rightarrow b=(m-n)c,\ (m-n)\in\Bbb Z\)

\(\therefore c\mid b\)

下面，我们通过一些习题，了解一下本节中证明题的解法，主要应用前面介绍的整除的基本性质。

习题 3.

题目思路解答

证明：若 \(m-p\mid (mn+qp)\)，则 \(m-p\mid (mq+np)\).

在这类“给定了一部分整除条件，要证明一个整除结论”的题目中，性质 3 的应用是常见的。

性质 3：如果 \(c\mid a,\ c\mid b\)，则对 \(\forall m,n\in\Bbb Z\)，有 \(c\mid ma+nb\).

对于这道题目而言，要证明 \(m-p\mid (mq+np)\)，并且给出了 \(m-p\mid (mn+qp)\) 这个条件，问题的关键就转化为：找到 \(m-p\) 的另一个倍数。

观察 \(mn+qp\) 和 \(mq+np\)，容易发现二者作差可以得到另一个倍数，从而问题得解。

证明：

\((mn+qp)-(mq+np)=mn-mq+qp-np=m(n-q)-p(n-q)=(m-p)(n-q)\)

要证：\(m-p\mid (mq+np)\)

只需证：\(m-p\mid (mn+qp)-(m-p)(n-q)\)

又由：\(m-p\mid (mn+qp)\)，\(m-p\mid (m-p)(n-q)\)

\(\therefore m-p\mid (mn+qp)-(m-p)(n-q)\)（性质 3）

即：\(m-p\mid (mq+np)\)

证毕。

在“习题 3.”中，我们找到了性质 3“如果 \(c\mid a,\ c\mid b\)，则对 \(\forall m,n\in\Bbb Z\)，有 \(c\mid ma+nb\)”，所需条件中的 \(a\) 和 \(b\)，并通过作差，确定了此性质中的 \(m\) 和 \(n\) 在本题中的值分别为 1 和 -1.

还有一类题目会给出所需条件中的 \(a\) 和 \(b\)，但性质中的 \(m\) 和 \(n\) 需要设法构造，例如：“习题 4*.”。

习题 4*.

题目思路解答

证明：若 \(p\mid (10a-b)\) 和 \(p\mid (10c-d)\)，则 \(p\mid (ad-bc)\).

看到题目的样式，可以想到使用性质 3；又因为已经给出了 \(p\) 的两个倍数，证明的关键转化为：

找到性质 3“如果 \(c\mid a,\ c\mid b\)，则对 \(\forall m,n\in\Bbb Z\)，有 \(c\mid \color{red}{m}\color{black}{a+}\color{red}{n}\color{black}{b}\)”中的 \(m\) 和 \(n\) 的值。

思考一下，\(m\) 和 \(n\) 分别是多少的时候，最容易消除 \((10a-b)\) 和 \((10c-d)\) 中数字 10 产生的影响，得到我们需要的 \((ad-bc)\) 呢？

证明：

\(ad-bc=(10a-b)\color{red}{c}\color{black}{+(10c-d)}\color{red}{(-a)}\)

又由：\(p\mid (10a-b)\)，\(p\mid (10c-d)\)

可得：\(p\mid (ad-bc)\)

证毕。

1.3 整除的两个定理

下面，我们再了解一下整除的两个定理，它们分别对于证明和计算，是可能有帮助的。

定理 1

定理

设 \(a,b\in\Bbb Z\)，其中 \(b\gt 0\)，则唯一 \(\exists q,r\in\Bbb Z\)，满足下式：\(a=bq+r,\ 0\leq r\lt b\).

其中:

\(q\) 称为 \(a\) 被 \(b\) 除得到的不完全商；

\(r\) 称为 \(a\) 被 \(b\) 除所得到的余数（或非负最小剩余），记作 \(a\ mod\ b=r\)，《数论讲义》中记为 \(<a>_{b}=r\). 。