信息安全数学基础笔记

<!-- toc -->

整除

定义：$\forall a, b \in Z, \exists q \in Z, (b \neq 0 \land a = q \times b) \Rightarrow b \mid a$

性质：

1. 传递性：$b \mid a \land a \mid c \Rightarrow b \mid c$

2. 线性组合中整除保持：$\forall a_1, s_1, a_2, s_2, ..., a_n, s_n \in Z, a_i \mid c \Rightarrow (a_1 s_1 + a_2 s_2 + ... + a_n s_n) \mid c$

素数

定义： 对于整数$p$，若$p \ne 0, \pm1 \land \neg\exists a, (a \ne \pm n, \pm 1 \land a \mid p)$，则称$p$为素数，否则$p$为合数

定理：

1. <a id="prime_1"></a>若$n$为正合数，$p$为$n$的一个非$1$最小因子，则$p$为素数且$p \le \sqrt{n}$

   证明：使用反证法，若p为合数，则$\exists b \in Z, b \mid p$，又有$p \mid n$，则由整除传递性得到$b \mid n$，因此$p$不是$n$的最小非$1$因子，与题设相矛盾。

   又由n为合数，则$\exists c \in Z, n = c \times p$，由于p为最小非1因子，故$c \ge p$，此时有$p \le c \lt n$，显然$p^2 \le n \Rightarrow p \le \sqrt{n}$

素数无穷

证明：基本思想是先假设素数有无限多个，然后证明可能在一个素数在这有限多个素数构成的集合之外。

假设素数有有限多个，则可以将其枚举为$P = \{p_1,p_2, p_3, ..., p_n\}$，假设有$n = p_1 p_2p_3 ... p_n + 1$那么必定有$\forall p \in P,n > p$。

假设$n$为素数，那么说明前提不正确，素数有无限多个。 假如$n$为合数。那么必定存在$p$为$n$的非$1$最小子。因此存在$a \in Z$使$n = p \times a$。若$p= p_j \in P$，则

因此有

此时

因此$a$不是整数，这与$a \in Z$为$n$的一个因子相盾，因此$p \notin P$（更准确的来说，此时$n$的所素因子都要比$P$中最大的元素还要大），因此素数有无多个。

上述证明过程利用了一类特殊的数——素数阶乘素数

扩展：证明形如$4k-1$的素数有无限多个

从上面对素数无限的证明，我们可以看到证明集合无限的核心思想是先去一个有限集合，然后证明总存在一个有限集合外的元素。这一过程需要通过构造来实现。

证明：假设有有限多个，那么这些素数可枚举为$P = \{p_1, p_2, ..., p_n\}$。考虑$m = 4 \times \prod_{p \in P}p - 1$，易知$\forall p_i \in P, \prod_{p \in P} > p_i$

若$m$为素数，则与开头假设相矛盾，可得$4k-1$形式的素数有无限多个。

若$m$为合数，假设m的所有素因子为$Q = \{q_1, q_2, ..., q_r\}$则$m = \prod_{q \in Q}q$

首先证明引理$\exists q_i \in Q, k \in Z, q_i = 4k-1$。由于Q中元素皆为素数，故$Q$中的一个元素$q_i$要么满足$4k-1$的形式，要么满足$4k+1$的形式，假设所有$q_i$满足$4k+1$的形式，易得$m$也一定满足$4k+1$形式，这与定义相矛盾。引理得证。

有上述引理可知存在$m$的素因子$q_i$具有$4k-1$的形式，若$q_i \notin P$，则与开头假设相矛盾，可得$4k-1$形式的素数有无限多个。

若$q_i \in P$，假设$q_i = p_i \in P$，则存在$c \in Z$使$m = c \times q_i$ 有：

即

故$c$不是整数，这与假设相矛盾，故$q_i \notin P$。与开头的假设相矛盾，证毕。（有问题，参见这里）

素数的算术基本定理

素数的算术基本定理：任何一个大于1的整数都可以写成素数的乘积，且该乘积唯一。

证明：

假设该整数为$n$，利用数学归纳法证明：

当$n$为素数时，有$p = n$为素数使$n = p$，定理成立

当$n$为合数时，将$n$分解为$p_1 \times n_2$，其中$p_1$为$n$的非1最小因子，有前面素数定理1我们可以得知$p_1$为素数。此时将$n_2$作同样的分解，最终我们可以得到$n = \prod_{i=0}^{k}p_i$，因此定理前半部分得证，后半部分可利用反证法证明，此处省略。

性质：

1. 将整数分解式写作

   $$n = \prod_{i=0}^{s}{p_i^{\alpha_i}}, \alpha_i \ge 0$$

   则对于$d$，当且仅当

   $$d = \prod_{i=0}^{s}{p_i^{\beta_i}}, \alpha_i \ge \beta \ge 0$$

   时，$d$为$n$的一个因子

最大公因数

定义： 几个整数$a_1, a_2, ..., a_n$的最大公因数记为$(a_1, a_2, ..., a_n)$。若$(a_1, a_2, ..., a_n) = 1$，则称它们互质。

性质：

1. <a id="gcd_1"></a>$a = b \cdot q + c \Rightarrow (a, b) = (b, c)$

   证明：假设$d = (a, b), d^{'} = (b, c)$，则

   $$d \mid a \land d \mid b \Rightarrow d \mid (a - b \cdot q = c)$$

   由于$d^{'}$是b与c的最大公因数，得到$d \le d^{'}$，同 理可得$d \ge d^{'}$，因此$d = d^{'}$

2. <a id="gcd_2"></a>假设$a, b, c \in Z$，且$b \ne 0 \land c \ne 0$，那么

   $$(a, c) = 1 \Rightarrow (ab, c) = (b, c)$$

   证明：

   假设$d_0 = (ab, c)$， $d_1 = (b, c)$，那么$d_1 \mid ab$，因此$d_1 \le d_0$。

   假设$ab = q_0d_0$，${c = q_1d_0}^{(1)}$，则$\frac{a}{c} = \frac{q_0}{q_1b}$，由于$(a, c) = 1$，易知$q_0 = ka$，${q_1b = kc}^{(2)}$。由式$(1)(2)$联立得$b = kd_0$，即$d_0 \mid b$，因此$d_0$为$(b, c)$的公因数，因此$d_0 \le d_1$

   综上所述，$d_0 = d_1$

   证毕（p.s. 也可以用广义欧几里得除法证）

   由上述定理我们可以得到：

   $$(a, c) = 1 \land c \mid ab \Rightarrow c \mid b$$

   一个特殊情况是$c$为素数时，$(a, c) = 1$必成立，此时

   $$\forall a, b: c \mid ab \Rightarrow c \mid b$$

3. 假设$a, b, u, v, p, q, s, t \in Z$且$abuv \ne 0$

   $$\begin{pmatrix}a \\ b\end{pmatrix} = \begin{pmatrix}p & s \\ q & t\end{pmatrix}\begin{pmatrix}u \\ v\end{pmatrix}, \begin{vmatrix}p & s \\ q & t\end{vmatrix} = 1$$

   则$(a, b) = (u, v)$。

   此性质描述了最大公因数在可逆变换（剪切，旋转）下的不变性。

4. $a, b \in Z \Rightarrow (2^a - 1, 2^b - 1) = 2^{(a, b)} - 1$

欧几里得除法

算法实现

注意到在上述定理中，我们可以得到一种逐步逼近a与b的最大公因数的方法——将计算$(a, b)$的问题转换成计算$(b, c)$的问题，从而保证每次迭代中c总会减小，最终减小到0，算法停机，代码实现如下：

pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

或者

let rec gcd a b = if b == 0 then a else gcd b (a mod b);;

贝祖等式

假设整数$a, b$的最大公约数为$d$，则等式

有整数解当且仅当$m$为$d$的倍数，且只要等式有解，它必然有无穷多解。

证明：

设$K = \{ax + by | (x, y) \in Z^2\}$，假设有$d_0 = ax_0 + by_0 \in K$，其中$d_0$为$K$中的最小正元素，以及$d_1 = ax_1 + by_1 \gt d_0$，假设

其中$q$为非负整数，$0 \le r \lt d_0$，则有

故$r \in K$，又因为$0 \le r \lt d_0$，注意$d_0$是$K$中的最小正整数，因此$r = 0$，因此$d_0 \mid d_1$，因此$\forall d \in K, d > 0 \Rightarrow d_0 | d$，特别的，$d_0 \mid a \land d_0 \mid b$，因此$d_0$为a与b的公约数，又因为对于a，b的任意一个公约数$d$，假设$a = l_ad, b = l_bd$，得到$ax_0 + by_0 = (l_ax_0 + l_by_0)d = d_0$，即$d | d_0$，因此$d$为$a$与$b$的最大公约数。

扩展欧几里得算法

有了贝祖等式后，我们可以得到$\exists x, y \in Z, ax + by = gcd(a, b)$，所谓扩展欧几里得算法即是求上述等式中$x$，$y$值的方法。

假设现在我们要求$d_0, d_1$的最大公约数，假设有：

$p_0d_0 - q_1d_1 = d_2$

$p_1d_1 - q_2d_2 = d_3$

$p_2d_2 - q_3d_3 = d_4$

$p_0 = p_1 = p_2 = 1$

由于$d_4$便是我们要求的最大公约数，我们只需要求出$xd_0 + yd_1 = d_4$中的$x, y$即可。假设$x_1d_1 + y_1d_2 = d_4$，我们首先可以导出:

$-p_1q_3d_1 + (p_2 + q_2q_3)d_2 = d_4$

因此有

$x_1 = p_1q_3$

$y_1 = p_2 - q_2q_3$

$x = p_0y_1$

$y = x_1 - q_1y_1$

可以看到，我们可以通过逐级上推最终确定$x, y$的值，这一过程可以通过递归来完成：

#[derive(Debug)]
pub struct ExtGCD {
    pub p: i64,
    pub q: i64,
    pub m: i64
}

pub fn ext_gcd(a: i64, b: i64) -> ExtGCD {
    if b == 0 {
        return ExtGCD {
            p: 1,
            q: 0,
            m: a
        }
    }
    
    let next = ext_gcd(b, a % b);

    ExtGCD {
        p: next.q,
        q: next.p - a / b * next.q,
        m: next.m
    }
}

最小公倍数

几个整数$a_1, a_2, a_3, ...$的最小公倍数记为$[a_1, a_2, a_3, ...]$

性质：

1. 假设$D$为$a, b$的最小公倍数，则

   $$[a, b] = \frac{ab}{(a, b)}$$

2. $$\forall a_1, ..., a_n \in Z: [a_1, a_2] = D_2, ..., [D_{n - 1}, a_n] = D_n \Rightarrow [a_1, ..., a_n] = D_n$$

   证明：使用归纳法证明：

   当$n = 2$时，显然成立。

   假设对$n - 1$结论成立，则有

   $$[a_1, a_2] = D_2, ..., [a_{n - 2}, a_{n - 1}] = D_{n-1} \Rightarrow [a_1, ..., a_{n-1}] = D_{n-1}$$

   对于$n$，假设$[a_1, ..., a_{n}] = D$，由于$[a_1, ..., a_{n-1}] = D_{n-1}$且$[D_{n-1}, a_n] = D_n$，可得$D_{n-1} \mid D$，$a_n \mid D$，进而$D_n \mid D \land D_n \le D$

   同时又易知$D_n$为$a_1, .., a_n$的公倍数，因此$D \le D_n$。

   综上所述，$D = D_n$，证毕。

3. <a id="lcm_3"></a>$\forall a_1, ..., a_n \in Z: a_i | D \Rightarrow [a_1, ..., a_n] = D$

   证明：省略，利用数学归纳法以及上面的性质2即可证明。

群（group）

定义：

群由一个集合和定义在该集合上的运算组成

使用$G$表示该集合，使用$\cdot$表示该运算。那么当代数结构$(G, \cdot)$满足下面的四条群公理时，该结构可以被称为群：

1. 封闭性：$\forall a, b \in G: a \cdot b \in G$

2. 结合律：$\forall a, b, c \in G: (a \cdot b) \cdot c = a \cdot (b \cdot c)$

3. 单位元存在性：$\exists e \in G: \forall a \in G: a \cdot e = e \cdot a = a$，可以将单位元（identity element）记为$1$

4. 逆元存在性：$\forall a \in G, \exists b \in G, a \cdot b = b \cdot a = e$，其中$e$为单位元，此时称$b$为$a$的逆元，记为$a^{-1}$

将二元运算$\cdot$称为该群上的乘法，那么由此可以导出该群上的除法：

假设有$a, b \in G$，现定义群上的除法$b / a = c \Leftrightarrow a \cdot c = b$。要证明除法的存在性即证明$c$的存在性。

那么根据群的逆元存在性可知一定存在$a$的逆元$a^{-1} \in G$使$a \cdot a^{-1} = 1$。因此由单位元的性质以及结合律有

因此$c \in G$。

群同态（Homomorphism）

定义：

假设$(G_1, \cdot)$与$(G_2, \circ)$为两个群，有映射$f: G_1 \rightarrow G_2$，假如

那么称$f$为群$G_1$到群$G_2$的一个同态。

若$f$为单射，则该同态为单同态，若$f$为满射，那么该同态是满同态。当$f$为一一对应（双射），那么该同态称为同构，记为$G_1 \cong G_2$。

当两个群同构时，这两个群拥有完全相同的群结构，本质上可以认为是同一个群。

一个群到其自身的同态/同构称为自同态/自同构。

性质：

1. 若$f$是$G_1$到$G_2$的一个同态，且这两个群的单位元分别为$e_1$与$e_2$，那么$f(e_1) = e_2$

   证明：// TODO

子群（subgroup）

定义：

对于群$(G, \cdot)$，若$H$为$G$的一个非空子集且同时与$G$的二元运算$\cdot$构成一个群，那么称$H, \cdot$为$G$的一个子群，群$(G, \cdot)$被称为该子群的母群，记为$H \le G$。

性质：

1. 对于每个群$G$，一元群$\{1_G\}$以及$G$自身都是它的子群，这两个子群被称为平凡子群。

2. $H \le G \Leftrightarrow \forall a, b \in H, a \cdot b^{-1} \in H$

   证明：只需证$H$是一个群即可。

   1. 单位元：假设$e_G$为$G$的单位元，那么令$a = b = x$，则$\forall x \in H, x \cdot x^{-1} = e_G \in H$，因此$H$的单位元为$e_G$

   2. 逆元：令$a = e_G, b = x$，则$\forall x \in H, e_G \cdot x^{-1} = x^{-1} \in H$，因此$H$中的每个元素都有逆元。

   3. 封闭性：即证$\forall m, n \in H, m \cdot n \in H$。令$a = m, b = n^{-1} \in H$（逆元存在性），则$\forall m, n \in H, a \cdot b^{-1} = m \cdot n \in H$

   综上所述，$H$是一个群。

举例：

对于整数加法群$(Z, +)$以及$nZ = \{nx \mid x \in Z\}, n \in Z^+$，$nZ$为$Z$的一个子群，并且$nZ$与$Z$同构。

证明：要证明$nZ$与$Z$同构，只需证明存在$Z$到$nZ$的一个双射$f$满足$\forall a, b \in Z, f(a + b) = f(a) + f(b)$，显然函数$f(x) = nx$满足条件，因此$nZ$与$Z$同构。

阿贝尔群（Abelian group）

定义：

对于群中的两个元素$a, b$，不一定有$a \cdot b = b \cdot a$，当一个群满足$\forall a, b \in G, a \cdot b = b \cdot a$时，该群被称为可交换的，也被称为阿贝尔群或者加法群、交换群（commutative group）。

当称一个阿贝尔群$G$为加法群时，可以将加法单位元记为$0$，群上的二元运算记为$+$。同时可以定义群上的减法$\forall a, b \in G, \exists c \in G, a - b = c \Leftrightarrow a = b + c$

半群（semigroup）

定义：

使用$G$表示该集合，使用$\cdot$表示集合上的运算。那么当代数结构$(G, \cdot)$满足

1. 结合律，即$\forall a, b \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)$

2. 封闭性，即$\forall a, b \in G, a \cdot b \in G$

时，该代数结构被称为半群。

当半群上存在单位元，即$\exists e \in G, \forall a \in G, a \cdot e = e \cdot a = a$时，该半群被称为幺半群（monoid），该单位元被称为幺元。

性质：

1. <a id="semigroup-1"></a>若$(G, \cdot)$为幺半群，记$G^*$为$G$中的可逆元素全体，那么$(G^*, \cdot)$是群。

   证明：

   1. 结合律与单位元：由于$(G, \cdot)$是幺半群，易知$(G^*, \cdot)$满足结合律，且单位元即为幺元

   2. 封闭性：现证$\forall a, b \in G^*, a \cdot b \in G^*$，即证$a \cdot b$存在逆元。有$a \cdot a^{-1} \cdot b \cdot b^{-1} = e \cdot e = e$，由结合律：$(a \cdot b) \cdot (a^{-1} \cdot b^{-1}) = e$，因此$a \cdot b$存在逆元$a^{-1} \cdot b^{-1}$。故$\cdot$在$G^*$上封闭。

   3. 逆元存在性：根据$G^*$的定义，这是显然的。

   综上所述，定理得证。

陪集（coset）

定义：

假设$G$为一个群，$H$为其子群，$g$为$G$中的元素，那么

1. $gH = \{g \cdot h | h \in H\}$为$H$在$G$中的左陪集

2. $Hg = \{h \cdot g | h \in H\}$为$H$在$G$中的右陪集

对于加法群，可以用$g + H$或者$H + g$来表示左/右陪集

注意我们可以从陪集的定义中导出一个关系：考虑$H$在$G$中的左陪集$gH$，一个元素$a \in G$在$gH$中当且仅当$\exists h \in H, a = g \cdot h$，即$a \cdot g^{-1} \in H$，这时我们定义群$G$上的关系$R(a, g) \Leftrightarrow a \cdot g^{-1} \in H$。

接下来我们证明该关系是一个等价关系：

1. 自反性：由子群的定义（单位元和母群相同）可知$g \cdot g^{-1} \in H$

2. 对称性：若有$a \cdot g^{-1} \in H$，由于$H$为群，有$(a \cdot g^{-1})^{-1} = g \cdot a^{-1} \in H$

   注意乘法的顺序反过来是因为默认乘法不可交换，因此$g \cdot a^{-1} \cdot a \cdot g^{-1} = g \cdot (a^{-1} \cdot a) \cdot g^{-1} = g \cdot g^{-1} = 1$ 。

3. 传递性：若$\exist b \in G, a \cdot b^{-1} \in H \land b \cdot g^{-1} \in H$，则由群的封闭性，有$a \cdot b^{-1} \cdot b \cdot g^{-1} = a \cdot g^{-1} \in H$

综上所述，关系$R(a, g)$是一个等价关系，即

我们可以看到，该等价关系导出的等价类即为$gH$，假设$R = \{g_i \mid i \in I\}$是$G$对上述等价关系的完全代表元系，根据等价类的性质，我们可以导出$G$在该等价关系下的划分：

该分割被称为$G$对子群$H$的左陪集分解，其中左陪集的个数为$|R|$，记为$[G:H]$，这个值被称为子群$H$对$G$的指数。

拉格朗日定理

对于有限群$G$，由于$G$可以被分割为$\bigcup_{g \in R}gH$，其中每个等价类$gH$的元素个数相同。显然$ord(H) | ord(G)$，即群$G$的阶为子群$H$的阶的倍数。

循环群

对于群$(G, \cdot)$，若存在$g \in G$使得$G = \{g^k | k \in \mathbb{Z}\}$，那么称$(G, \cdot)$为一个循环群，其中$g$为该循环群的生成元。

循环群的阶

有限群$G$​中所有元素的个数称为群的阶，记为$ord(G)$​。

当$G$是阶为$n$的循环群时，有

对于$G$中的元素$a$，$H = (\{a^k | k \in \mathbb{Z}\}, \cdot)$构成一个循环群，该群为$G$的子群。其阶$ord(H)$也被称为$a$在$G$中的阶，记为$ord(a)$。当$ord(H) = ord(a) = ord(G)$时，$a$称为$G$的生成元。

假设$a = g^k$，为了求$H$的阶$ord(G) = m$，我们需要得到最小的$m$，使得$a^m = g^{km} = e$。由于$g^n = e$，我们只需求出最小的$m$使$n | km$。不难得到

即$a$的阶为$\frac{n}{gcd(n, k)}$。

推论

1. 对于阶为$n$的有限循环群$G$，其生成元的个数为$\phi(n)$。

   证明：要使某一元素$a = g^k, (k \lt n)$为群的生成元，只需$n = \frac{n}{gcd(n, k)}$，即$n, k$互质，显然，这样的$k$的个数即为欧拉函数$\phi(n)$。（同时可以证明$k \lt n$时，幂乘不会得到自身）

2. 阶为质数的群都是循环群。

   证明：// TODO

环（ring）

定义：

假设有一个集合$R$以及定义在该集合上的二元运算$\cdot$以及$+$，三元组$(R, +, \cdot)$形成一个代数结构，当且仅当该代数结构满足下面条件时，其被称为一个环：

1. $(R, +)$形成一个交换群

2. $(R, \cdot)$形成一个半群

3. 乘法运算（$\cdot$）关于加法（$+$）满足分配律，即$\forall a, b, c \in R, a \cdot (b + c) = a \cdot b + a \cdot c$

性质：

环的性质可以由其定义导出

1. 交换群$(R, +)$的单位元被称为0元素，有$0 + 0 = 0$。同时有$\forall a \in R, a \cdot 0 = 0 \cdot a = 0$

   证明：

   由分配律：

   $$a \cdot 0 = a \cdot (0 + 0) = a \cdot 0 + a \cdot 0$$

   因此：

   $$a \cdot 0 - a \cdot 0 = a \cdot 0$$

   注意上面的$-$是加法群的逆运算，由乘法半群的封闭性以及加法群逆运算的定义知$a \cdot 0 - a \cdot 0 = 0$，因此$a \cdot 0 = 0$

   同理可证$0 \cdot a = 0$.（注意这个不是半群的单位元）

2. $\forall a, b \in R, a \cdot (-b) = (-a) \cdot b = - a \cdot b$

   证明：

   由分配律：

   $$a \cdot (-b) = a \cdot (0 - b) = a \cdot 0 - a \cdot b = -a \cdot b$$

   同理有$(-a) \cdot b = - a \cdot b$，原式得证。

幺环（unital ring）

定义：

当半群$(R, \cdot)$存在单位元（为幺半群）时，该环被称为幺环。此时幺半群的幺元也是该幺环的幺元。

环的理想（ideal）

定义：

若一个环的一个子集上的加法运算形成一个群，同时所有与子环中的元素进行的乘法运算的结构均在该子环中，那么称该子环称为原环的理想。环的理想呈现出一种闭包（对加法封闭）和吸收（对乘法吸收）的性质，因此可以利用环的理想来构造商环，从而实现对原环进行某种聚类。

严格定义如下：

假设有环$(R, +, \cdot)$，$I \subseteq R$，那么当

1. $(I, +)$构成$(R, +)$的子群

2. $\forall i \in I, \forall r \in R, i \cdot r \in I$时，$I$被称为$R$的一个左理想。$\forall i \in I, \forall r \in R, r \cdot i \in I$时，$I$被称为$R$的一个右理想。当$I$既是$R$的左理想，也是右理想时，称其为$R$的一个双边理想，简称理想。

举例：整数环$Z$只有$nZ$形式的理想

商环 (quotient ring)

定义：

假设$R$是一个环，$I$是它的一个（双边）理想，定义如下等价关系（满足自反，传递，对称性）：

使用$R/I$来表示由这个等价关系导出的等价类的集合，其中的元素记为$a + I$。注意这个元素是一个集合，准确的来讲，$a + I = \{a + x \mid x \in I\}$。

对于集合$R/I$

//TODO

剩余（residual）类与剩余系

同余（congruence）

定义：

注：$a \equiv b \pmod m$也可以写作$m \mid a - b$

性质：

1. 同余具有自反性，对称性以及传递性。

2. $da \equiv db \pmod m \land (d, m) = 1 \Rightarrow a \equiv b \pmod m$

   证明：易知$m \mid da - db$，由于$(m, d) = 1$，由最大公因数的性质2可知$m \mid a - b$，因此$a \equiv b \pmod m$成立。

3. $\forall m, d \in Z^+: a \equiv b \pmod m \Rightarrow ad + bd \pmod {md}$

4. $\forall m \in Z^+: a \equiv b \pmod m \land (a, b, m) \mid d \Rightarrow \frac{a}{d} + \frac{b}{d} \pmod {\frac{m}{d}}$

5. $\forall m \in Z^+: a \equiv b \pmod m \land d \mid m \Rightarrow a \equiv b \pmod {d}$

6. $\forall m_1, ..., m_k \in Z^+: a \equiv b \pmod {m_i} \Rightarrow a\equiv b \pmod {[m_1, ..., m_k]}$

   证明：利用上面提到的最小公倍数的第三条性质，这是显然的。

7. $a \equiv b \pmod m \Rightarrow (a, m) = (b, m)$

   证明：易知$a = qb + m$，利用最大公因数的性质1即可证明。

Definition: A group view

定义一个等价关系

那么我们可以在整数集$Z$上可以由该等价关系导出一个分割。这个分割由$n$个等价类组成，将包含$0 <= i < n$的一个等价类记为$\overline{i}$。使用$Z_n$表示上述$n$个等价类组成的集合，在$Z_n$上定义加法

现证明该集合是一个阿贝尔群。

1. 由同余的性质，该加法显然成立并且满足交换律，结合律以及封闭性。

2. 单位元：易知我们总是有$\overline{0} \in Z_n$，且有$\overline{0} + \overline{a} = \overline{a} + \overline{0} = \overline{a}$，因此$\overline{0}$为单位元。

3. 逆元：根据同余的性质，有$\overline{0} - \overline{a} = \overline{-a}$，因此对于每个$\overline{a} \in Z_n$，总有$\overline{-a} \in Z_n$使$\overline{a} + \overline{-a} = \overline{0}$。

综上所述，$Z_n$是一个阿贝尔群。这个群被称为整数模n加法群。

该群中的等价类称为模$n$剩余类，这个中所有等价类的代表元组成的集合被称为一个模$n$完全剩余系。

Definition: A ring view

在上面提出的整数模$n$加法群$Z_n$上假如定义一个乘法$\overline{a} \cdot \overline{b} = \overline{a \cdot b}$。我们下面证明整数群在这一二元关系下形成一个幺半群：

1. 封闭性：由于任何一个整数必然属于某一个等价类，因此这是显然的

2. 结合律：根据乘法的定义，这同样是显然的

3. 单位元：由于$\overline{a} \cdot \overline{1} = \overline{1} \cdot \overline{a} = \cdot \overline{1}$，可知$\overline{1}$为单位元。

综上所述，$Z_n$对此乘法形成一个含幺交换半群。

根据环的定义可知$(Z_n, +, \cdot)$构成一个幺环。

整数模n乘法群

接下来我们研究含幺交换乘法半群$(Z_n, \cdot)$，通过上面提到的含幺半群的性质，我们可以知道从这个半群中可以提取出一个所有元素均可逆的子集$Z_n^*$，这个子集在乘法运算上构成群。

首先我们来研究该半群中的哪些元素可逆：

对于该条件的形式描述为

即$1 \equiv ab \pmod n$，即$(ab, n) = 1$。

下面我们简化问题：若$\forall a \in Z, \exists b \in Z, (ab, n) = 1$，求$a$应当满足的关系。

由上面提到的关于最小公因数的定理我们可以知道

此时取$b = a$即可使$(ab, n) = 1$。

因此我们推测

但注意这这里我们仅仅证明了充分性，下面我们来证明其必要性，即证明

显然当$(a, n) \ne 1$时有$d_1 = (a, n) \ne 1$，进而$d_1 \mid ab$，显然$(ab, n) \ge d_1 \ne 1$。故必要性得证。