Group, ring and field

这几个概念的条件是逐渐叠加的：

Group

定义：

1. a set with an operation $\cdot:G\times G\to G$
2. associativity
3. identity $e$: $\exists e\in G\forall a\in G\implies a\cdot e=e\cdot a=a$
4. inverses: $\forall a\in G\exists b\in G\to a\cdot b=b\cdot a=e$

group 的定义不要求运算具有可交换性，

如果group 的运算满足可交换性，就将这个group称作 abelian group.

group 的元素的 inverse 有且只有 $1$ 个。否则，令 $a\in G$，两个inverse $b_1$ and $b_2$，$ab_1=ab_2=e$，

Ring

Ring 是有两个运算 $+$ 和 $\cdot$ 以及两个特殊元素 $0$ 和 $1$ 的集合 $R$：

• $R$ with $+$ 是 abelian group，identity 是 $0$ 。也就是说除了上面列出来的4条性质以外，还满足 commutative；
• $R$ with $\cdot$ 满足 associativity，$1$ 是该运算下的 identity，不要求是group；
• $R$ with $+$ and $\cdot$ 满足 distributive。

此外，在ring的定义的基础上增加乘法的交换律，是为commutative ring，比如整数$\mathbb{Z}$，有理数$\mathbb{Q}$，实数$\mathbb{R}$，复数$\mathbb{C}$和整数同余类 $\mathbb{Z}/m\mathbb{Z}$。

Unit

在 commutative ring 中，如果一个元素 $a$ 满足存在对应的元素 $b$ 使得 $a\cdot b=b\cdot a=1$ 就称之为 unit。严格来说 unit 也不能说是乘法运算的inverse，因为这儿没要求满足乘法group；但是 $a$ 对应的 unit $b$ 如果存在，就必然是唯一的，可以用上边group inverse类似的方法得到这个结论。

Zero divisor

在 ring 中，如果两个非零元素相乘等于零，这两个元素就称为 zero divisor，而且互为 complementary zero divisor。比如，在 $\mathbb{Z}/4\mathbb{Z}$ 中，$2$ 就是 zero divisor。

• 有限 ring 里面的任意非0元素，要么是 zero divisor 要么是 unit。
• (乘法的cancellation) 如果非零元素 $a$ 不是 zero divisor，那么 $ab=ac\implies b=c$

Ring homomorphism

定义从 $f: R\to S$，$R$ 和 $S$ 均为 ring。如果 $f$ 满足：

1. $\forall r,r’\in R\to f(r+r’)=f(r)+f(r’)$
2. $\forall r,r’\in R\to f(r\cdot r’)=f(r)\cdot f(r’)$
3. $f(1)=1$

就称 $f$ 为 ring homomorphism 。虽然有点绕口，但是还得说明一下在上述三个条件中，等号左边的 $+$，$\cdot$ 和 $1$ 分别是 $R$ 的两个运算和 $R$ 的乘法运算的identity；等号右边的 $+$，$\cdot$ 和 $1$ 分别是 $S$ 的两个运算和 $S$ 的乘法运算的identity。。

Field

在 commutative ring 的基础上，如果满足以下就称之为 field:

• inverses: 非零元素以外所有的元素都是 unit；
• non-triviality: 至少有两个元素

More on Group

重新来看定义：

1. a set with an operation $*:G\times G\to G$
2. associativity
3. (1893)cancellation and solvability,
4. (现代的定义)or existence of identity and inverses

定义中存在冗余，第三点和第四点是等价的；可以利用 identity 和 inverses 证明 cancellation 和 solvability。要注意定义并没有要求运算满足可交换性：

证明 cancellation 这儿跟上边 ring 的乘法cancellation不同：

证明 solvability $\forall a,b \in G$ ，令 $c=a’*b$。现在要证明 $k=c$ 就是满足 $ak=b$的值。首先，$a’,b\in G\implies c\in G\text{(closure)}$，也就是存在性。

反过来，可以利用 cancellation 和 solvability 来证明 identity 和 inverse：

证明 identity

证明 inverse 首先根据 solvability 可知$\forall a\in G, \exists b\in G\to ab=e$ 以及 $\exists c\in G\to bc=e$。然后需要证明 $ab=ba=e$：

identity以及每个元素对应的inverse也只有一个，可以用cancellation性质来证明。

$U_m$

$\mathbb{Z}/m\mathbb{Z}$ 的所有 unit ($\gcd([a],[m])=[1]$) 组成的集合

加上模$m$ 乘法是一个group，记为 $U_m$。

• identity: 显然 $[1]\in U_m$。
• closure: 模 $m$ 乘法在集合 $U_m$ 上是闭合的，这是因为两个 unit $[a]$ 和 $[b]$ 的积也是一个 unit。
  • 分别写出$[a]$和$[b]$各自和 $[m]$ 的贝祖等式的结果并且相乘，并且对乘积模 $[m]$，观察结果。
• inverse: 由贝祖定理可知 $\forall a\in U_m\exists x’,y’\in\mathbb{Z}\to ax’+my’=1\implies ax’=1\pmod{m}$，$x’\pmod{m}\in U_m$，因此inverse存在。

Abstract Fermat Theorem

对于一个长度为 $n$ 的有限abelian group $G$ 中的任意元素 $a$，都满足 $a^n=e$。

欧拉定理 是本定理的推论。

Subgroup

subgroup 是满足group定义的子集合。前面提到 group 的有两个点：identity 和 inverse；实际上subgroup可以定义为closure under operation的 $G$ 的子集合，光是这一点就已经蕴含了 identity 以及 inverse 了。给定一个group $G$ 的子集合 $H$，如果运算在 $H$ 上是闭合的，那么根据上面提到的Abstract Fermat Theorem，$e$ 必存在于 $H$；又 $a^{n}=a^{1+n-1}=a\times a^{n-1}=e$，因此 inverse 也存在。所以closure under operation是subgroup的充分条件。

对于一个group $G$，trivial subgroup 是:

• 仅包含 identity 元素的group，或者
• $G$ 自身。

可见 trivial group 只有两个。而 nontrivial group 即是除去两个 trivial subgroup 以外的其他子集。

命题 如果一个有限 abelian group $G$ 的长度不为 $1$ 且不为质数，那么 $G$ 至少有一个nontrivial subgroup。

那么如果 $G$ 的长度 $n=p$ 是质数，是不是就不存在nontrivial subgroup？答曰、是的。举个例子，$\langle7\rangle \text{ over }\mathbb{F}_9 = {1,4,7}$ 就是一个长度为3的group，这个group也没有nontrivial subgroup。

质数长度的 group $G$ 中对所有元素的order 都是 $p$，这一点可用反证法证明。对于当中的任意一个元素 $a$，由上面的 Abstract Fermat Theorem 可知 $a^p=1$。假设 $a$ 的 order 为 $d<p$，$p=dq+r$，$r\lt d$；加上 $p$ 是质数，所以$0\lt r\lt d$。因此利用 $a^d=1$ 得到 $a^p=a^{dq+r}=a^{r}=1$，这跟order的定义——“$d$ 是满足 $a^n=1$ 的最小正整数”矛盾，因此假设不成立；也就是说长度为质数 $p$ 的group中、所有元素的order都是 $p$；不存在小于 $p$ 且 $a^r=1$ 的整数 $r$，也就不存在nontrivial subgroup。

这么看来质数长度的group跟质数挺像的，都是无法继续分解为更小的group（整数）。

Cyclic subgroup

固定来自 $G$ 的一个元素$a$，定义 cyclic subgroup 为 $a$ 的所有正整数 $n$ 次幂 $a^n$ 的集合，用 $\langle a \rangle$ 表示；当 $n>0$，$a^n=a\cdot a\cdot\cdots\cdot a$，$a^{-n}=a^{-1}\cdot a^{-1}\cdot\cdots\cdot a^{-1}$。

如果一个group $G$中的元素 $b$ 满足$\langle b\rangle=G$，那么称 $G$ 是 cyclic 的。

是不是存在非cyclic的subgroup呢？首先，由于group的运算的closure性质，一个group必然包含cyclic subgroup，所以可以通过把多个cyclic subgroup合并一起、然后用closure性质把不在subgroup的元素加进去。举个例子，在$\mathbb{Z}/15\mathbb{Z}$中，用以下代码计算

for i in range(15):
    print(f'<{i}>={set([i**j%15 for j in range(15) if j > 0])}')

去掉不满足group定义的结果、剩余下面 8个cyclic group

<1>={1}
<2>={8, 1, 2, 4}
<4>={1, 4}
<7>={1, 4, 13, 7}
<8>={8, 1, 2, 4}
<11>={1, 11}
<13>={1, 4, 13, 7}
<14>={1, 14}

把$\langle4\rangle$、$\langle11\rangle$和$\langle 14\rangle$合并得到 $\lbrace 1,4,11,14\rbrace$，这是一个subgroup却不是一个cyclic subgroup。

命题 任意一个来自有限 group $G$的元素 $a$ 的order等于cyclic group $\langle a\rangle$的元素的数量。

先复习一下order的定义: 在 group 中，元素 $a$ 的 order 是满足 $a^d=1$ 的最小正整数。

证明这个命题的思路就是证明以下两个集合相等

首先证明 $d\le n$、因此$A$中的每个元素都存在于 $\langle a\rangle$中；然后反过来，利用 $n=dq+r\text{,}(r\lt d)$证明 $\langle a\rangle$ 中的每个元素都存在于 $A$ 中；最后证明 $A$ 的元素两两不同。

如果 $a$ 的order $d=rs$ 是一个合数，$a^d=a^{rs}={a^r}^s$，这说明 $a^r$ 的order 为 $s$，而且这也是 cyclic group $\langle a^r\rangle$ 的长度。

coset

给定运算为 $*$ 的 group $G$ 以及 subgroup $H$，对于 $G$ 当中任意一个元素 $b$ ，将集合

称为 $b$ 的 left coset，记作 $b*H$ 。

coset 是一个集合，不一定是group ，因为coset不一定满足group的定义。

模 $m$ 同余类就是一种coset。$\mathbb{Z}$ 是一个加法 group，identity是 $0$，$a\in\mathbb{Z}$ 的逆是 $-a$。$m\mathbb{Z}$ 是 $\mathbb{Z}$ 的一个subgroup ，对于任意整数 $i$ 都有对应的coset $i+m\mathbb{Z}$，也就是同余类 $[i]_m$。任意两个同余类要么是相等的、要么是不相交的；类似地，两个 coset 也是要么相等要么相交。

如果 $\exists t\in a\times H$ 且 $t\in b\times H$ ，就可以令 $t=ah_1=bh_2$。 $\forall a\times h’\in a*H$，由于 group的 solvability，$\exists k \to h’=h_1k$；因此 $ah’=ah_1k=bh_2k$ ；因为 $h_2,k\in H$， $h_2k\in H$ ，所以 $bh_2k\in b\times H$ ，这说明任意 $a\times H$ 中的元素都存在于 $b\times H$ ，也就是说 $a\times H\subseteq b\times H$ ；同理，反之亦然。因此 $a\times H=b\times H$ 。

除此之外，$b*H$ 的长度和 $H$ 的长度相等。

Lagrange’s Theorem

有限 group $G$ 的任意一个 subgroup $H$ 都满足 $\mid H\mid$ 整除 $\mid G\mid$。需要利用上面 coset 的性质来证明。

有限group的长度也称之为 order，而cyclic group $\langle a\rangle$ 的 order 和 $a$ 的order是相等的。另外拉格朗日定理也可以换一种说法：有限group $G$ 的subgroup $H$ 的order整除 $G$ 的 order。而 $H$ 的 coset 的数量又称之为 index 。

$n$-th root 集合

令 $U_m(n)=\lbrace [a]\in U_m\mid [a]^{n}=[1]\rbrace$ 表示$n$次方根的集合，乘法在这个集合上也是闭合的，$U_m(n)$ 是 $U_m$ 的subgroup。

命题 $d=\gcd(m-1,\varphi(m))\implies U_{m}(m-1)=U_m(d)$。由贝祖定理可知 $\exists x,y\in\mathbb{Z}\to (m-1)x+\varphi(m)y=d$

这说明 $m-1$ 次方根同时也是 $d$ 次方根，也就是 $U_m(m-1)\subseteq U_m(d)$。反过来由于 $d\mid {m-1}$，$d$ 次方根同时也是 $m-1$ 次方根，也就是$U_m(d)\subseteq U_m(m-1)$，因此 $U_m(m-1)=U_m(d)\square$。

• Previous
  数论学习笔记 - RSA算法的数学原理
• Next
  String Encoding