群的定义

group 是一个 pair, (G,⋅)(G,\cdot) 其中 GG 是一个 集合，且符号 ⋅\cdot 表示 G×G→GG \times G \to G (g,h)→g⋅h=gh(g,h)\to g\cdot h = gh 是 composition 符号
群具有如下性质:

  1. 符号 ⋅\cdot 具有 结合律 (ab)c=a(bc)(ab)c = a(bc)
  2. GG 中包含了单位元素 1, 从而有 1a=a1=a1a = a1 = a 对所有 a∈Ga\in G
  3. 所有元素 a∈Ga\in G可逆，即存在 一个元素 bb 使得 ab=ba=1ab = ba = 1

阿贝尔群 Abelian Group

是一个composition符号可以交换(commutative)的群，即 ab=baab = ba

常用定理

对于一个群 GG, a,b,c∈Ga,b,c\in G, 那么：

  1. 存在唯一单位元
  2. ba=ca⇒b=cba = ca \Rightarrow b = c 且有 ab=ac⇒b=cab = ac \Rightarrow b = c
    1. 说明等号可以从前后同时约去一个值
    2. 证明：
  3. 对于所有 a∈Ga\in G 我们都有唯一元素 b∈Gb\in G 使得 ab=ba=1ab =ba = 1
  4. (ab)−1=b−1a−1(ab)^{-1} = b^{-1}a^{-1}

子群 Subgroup

子群不同于子集，其有 “空间闭合” 的要求，那么我们会非常好奇于如何将一个群分割成多个子群，就像线性空间可以被拆解为 线性无关的子空间一样

定义

对一个群 GG 的子群 HH 有以下的性质

  1. 闭合 Closure: 如果 a,b∈Ha,b\in H, 那么 ab∈Hab\in H
  2. 单位元 Identity: 1∈H1\in H
  3. 逆元 Inverse: 如果 a∈Ha\in H, 那么 a−1∈Ha^{-1}\in H

加法群的子群

一个子群 (Z,+)(\mathbb Z,+) 是一个子群，如果:

  1. Closure: 若 a,b∈Ha,b\in H, 那么 a+b∈Ha+b\in H
  2. Identity: 0∈H0\in H
  3. Inverse: 若 a∈Ha\in H, 那么 −a∈H-a\in H
    对于所有 a∈Za\in \mathbb Z, 那么整数加法群 (Z,+)(\mathbb Z,+) 的子群是 aZ={n∈Z∣n=ka对于某些k∈Z}a\mathbb Z = \{n\in \mathbb Z| n = ka 对于某些 k\in \mathbb Z\}
    这就是对 n 求倍数的一个群
大小比较

我们写 H≤GH\le G 如果 HH 是一个 G 的子群，且 H<GH < G 如果 H≤GH\le G 且 H≠GH \not = G

加法子群的定理

令 SS 是一个 加法群 (Z,+)(\mathbb Z, +) 的子群，那么

  1. SS 是一个 简单的子群 ({0})(\{0\})
  2. 或者其满足形式 (aZ)(a\mathbb Z)， 其中 a 表示S中最小的正数元素
注

也就是说，整数空间可以被加法群分割成倍数子群

证明

由于 S 是一个子群，则 0∈S0\in S, 若 S={0}S = \{0\} 则满足条件1， 条件得证
如果 S≠{0}S\not = \{0\}, 那么 SS 中必然存在一个正数元素，我们令 aa 为其中最小的正数元素（这个依赖于正整数的良序性）那么我们需要证明：

  1. aZ⊂Sa\mathbb Z\subset S: 令 z∈aZz\in a\mathbb Z, 那么 z=kaz = ka 对于某个 k∈Zk\in \mathbb Z, 由于 k∈Zk\in \mathbb Z, 令z>0z > 0, 那么既然 a∈Sa\in S, 则 ka∈Ska \in S 通过 递归和闭合性得到，且 −ka∈S-ka\in S 也存在，通过相反数定理。相似的，对 z<0z < 0 也成立
  2. S⊂aZS\subset a\mathbb Z : 令 s∈Ss\in S, 那么 s=qa+rs = qa + r 对于某个 q∈Z,0≤r<aq\in \mathbb Z, 0\le r < a, 由于 k∈Zk\in \mathbb Z, 令s>0s > 0, 那么既然 a∈Sa\in S, 则 qa∈Sqa \in S 通过 递归和闭合性得到，且 r−qa∈Sr-qa\in S 也存在, 但是 a 才是 S 中最小的正整数，所以 r=0r = 0, 即 n=qan = qa 对 q∈Zq\in \mathbb Z 成立，所以 s∈aZs\in a\mathbb Z

子群的生成 Generation

我们称 群 GG 是由 a 和 b 生成的，写作

S = a\mathbb Z + b\mathbb Z = \{n\in \mathbb Z\ |\ n = ra + sb\ 对某些\ r,s\in \mathbb Z \}$$ 这也是包含 $a\mathbb Z$ 和 $b\mathbb Z$ 的最小子群 #### 子群逆性质 如果 $S\subset \mathbb Z$ 是整数加法群的一个子群，那么存在 $d\in \mathbb Z$ 使得 $S = d\mathbb Z$ #### 生成群定理 令 $a,b\in\mathbb Z$ 而都为 0, 且 令 $d$ 是一个正整数 生成子群 $S = a\mathbb Z + b \mathbb Z$ 即 $d\mathbb Z = a\mathbb Z + b \mathbb Z$ 那么： 1. $d\ |\ a$ 且 $d\ |\ b$ 1. 因为 $a\in d\mathbb Z$ 所以 $a = kd$ 对于某个 $k\in \mathbb Z$ 2. 对于 $e\in \mathbb Z$ 如果 $e\ |\ a$ 且 $e\ |\ b$ 那么 $e\ |\ d$ 1. 令 $e\in \mathbb Z$ 且 $e\ |\ a$ 且 $e\ |\ b$ 那么 $a = ke$ 且 $b = le$ 对于某个 $k,l\in \mathbb Z$ 那么 $d = ra + sb = rke + sle = e(rk + sl)$ 所以 $e\ |\ d$ 3. 存在整数 $r,s$ 使得 $d = ra + sb$ 1. 由于 $d\in a\mathbb Z + b\mathbb Z$ 所以 $d = ra + sb$ 对于某个 $r,s\in \mathbb Z$ 你应该能发现， $d =gcd(a,b)$ #### Bezout 恒等式 对于 $a,b\in \mathbb Z$, 当且仅当 存在整数 $r,s$ 使得 $ra + sb = 1$ 使得 $gcd(a,b) = 1$, 即 a,b 互质， ##### 证明 将上述 a,b 互质就可以得到 #### 推论 令 $p$ 为一个质数，且 $a,b\in \mathbb Z$, 如果有 $p | ab$ 那么 $p\ |\ a$ 或者 $p\ |\ b$. 也可以写作 $c\ |\ ab$ 且 $gcd(c,b) = 1$ 那么 $c\ |\ a$ ##### 证明 假设 $p\ \not| \ a$ 那么 $gcd(a,p) = 1$, 因此 $\exists r,s\in \mathbb Z$ 使得 $ra + sp = 1$. 那么因此 $rab + spb = b$ 由于 $p\ |\ ab$， $p\ |\ rab$, $p\ |\ spb$ 所以 $p\ |\ b$ ##### 注 将上述定理递推我们就有 $p\ |\ a_1a_2\cdots a_n$ 那么 $p\ |\ a_i$ 对于某个 $i$ ## 代数基本定理 Fundamental Theorem of Arithmetic ### 定理内容 任何一个正整数可以被写作唯一的 (有序的) 质数的乘积 其中，1 写作质数空集的乘积 ### 证明 #### 存在性 对于 $n > 1$ 那么要么 $n$ 是质数，要么可以被拆成 $n = p\cdot (n/p)$ 的乘积对于某些质数 p, 再写下去就可以得到了命题 #### 唯一性 假设 $n = p_1\cdots p_r = q_1 \cdots q_s$ 其中 $p_i, q_i$ 都是质数，那么 $p\ |\ q_1\cdots q_s$ 那么 必然有 $p\ |\ q_i$ 对某个 $i$ 成立，但是都是质数，所以 $p = q_i$ 通过对称性得到 $q = p_i$ 从而得到唯一性 ### 黎曼 Zeta 函数 $$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p\in \mathbb P}\frac{1}{1-p^{-s}}

狄利克雷定理

对于 u,v∈Zu,v\in \mathbb Z, 那么 gcd(u,v)=1gcd(u,v) = 1 的概率是 ζ(2)−1=6π2\zeta(2)^{-1} = \frac{6}{\pi^2}

最小公倍数 LCM least common multiple

对于 a,b∈Za,b\in \mathbb Z 且令 m = lcm (a,b)\text{m = lcm (a,b)} 是其最小公倍数，那么m也是最小的正整数生成 aZ∩bZa\mathbb Z\cap b\mathbb Z 即

mZ=aZ∩bZm\mathbb Z = a\mathbb Z \cap b\mathbb Z

注

如果 n=a1⋯ann = a_1\cdots a_n 那么有 lcm(a1,⋯ ,an) ∣ n\text{lcm}(a_1,\cdots, a_n)\ |\ n

推论：gcd 与 lcm 的关系

对于 a,b∈N\{0}a,b\in \mathbb N \backslash \{0\} 我们有 d=gcd(a,b),m=lcm(a,b)d = gcd(a,b), m = lcm(a,b) 那么我们有 ab=dmab = dm

证

因为 b/d∈Zb/d\in \mathbb Z 那么 ab/d∈aZab/d \in a\mathbb Z 且相似的 ab/d∈bZab / d\in b\mathbb Z
因此，我们有 ab/d∈aZ∩bZ=mZab / d \in a\mathbb Z \cap b \mathbb Z = m\mathbb Z 因此 md ∣ abmd\ |\ ab
因此 m/b∈Zm/b\in \mathbb Z 且有 a ∣ ma\ |\ m 那么 a ∣ b⋅mb⇔ad ∣ mb⇔ab ∣ dma\ |\ b\cdot \frac{m}{b} \Leftrightarrow \frac{a}{d}\ |\ \frac{m}{b} \Leftrightarrow ab\ |\ dm
互相整除，因此二者相等