想系统地学习一下近世代数，参考书是Joseph-Gallian的《Contemporary Abstract Algebra》，希望花半年时间读完，在博客里做笔记督促自己。
很多抽象代数的关注点在整数和集合的特性，为未来的学习方便，这节介绍一些基础的结论。
良序性（视为公理）：
任何正整数的非空集合都包含一个最小的数。
对于 s , t ∈ Z s,t\in Z s,t∈Z
∀ a , b ∈ Z , b > 0 → ∃ ! q , r ∈ Z , a = b q + r ∧ 0 ≤ r < b \forall a,b\in Z, b>0\to \exists !\ q,r\in Z,a=bq+r\ \land\ 0\le r<b ∀a,b∈Z,b>0→∃! q,r∈Z,a=bq+r ∧ 0≤r<b
约定符号 ∃ ! \exists ! ∃!表示存在唯一的元素。
定理含义：这个定理描述了整数相除的结果， a a a是被除数， b b b是除数， q q q是商， r r r是余数。这里还限制了除数大于0，余数非负且余数必须小于除数，这样才能保证商和余数的唯一性。
证明：考虑一个集合 S = { a − b k ∣ k ∈ Z , a − b k ≥ 0 } S=\{a-bk\mid k\in Z,a-bk\ge 0\} S={a−bk∣k∈Z,a−bk≥0}
显然，集合是非空的，这很好证明，著需要选取适当的 k k k使得 a − b k ≥ 0 a-bk\ge 0 a−bk≥0即可，这里可以简单取 k = − b ∣ a ∣ k=-b|a| k=−b∣a∣
如果 0 ∈ S 0\in S 0∈S，那么 b ∣ a b\mid a b∣a，此时必有 r = 0 , q = a / b r=0,q=a/b r=0,q=a/b，这取法是唯一的；
如果 0 ∉ S 0\notin S 0∈/S，根据良序性，集合必然存在一个最小的正数，不妨设为 r r r，此时有 a = b q + r , r ≥ 0 a=bq+r,r\ge 0 a=bq+r,r≥0，此时只需要证明 r < b r< b r<b即可。如果 r ≥ b r\ge b r≥b，很容易确定， r r r并非 S S S中最小的数，只需将 k k k增加1 ( a > 0 a>0 a>0的情况， a < 0 a<0 a<0则相反），那么必有 r − b ∈ S r-b\in S r−b∈S。
QED
∀ a , b ∈ Z , a ≠ 0 , b ≠ 0 → ∃ s , t ∈ Z , gcd ( a , b ) = a s + b t \forall a,b\in Z, a\neq 0, b\neq 0\to \exists s,t\in Z\ ,\gcd(a,b)=as+bt ∀a,b∈Z,a=0,b=0→∃s,t∈Z ,gcd(a,b)=as+bt
gcd ( a , b ) = min { a s + b t ∣ a s + b t > 0 } \gcd(a,b)=\min\{as+bt\mid as+bt>0\} gcd(a,b)=min{as+bt∣as+bt>0}
定理含义：这个定理说明，两个整数的最大公约数可以写成这两个数的线性组合，且最大公约数是这两个数的所有线性组合中，最小的正整数。
证明：考虑集合 S = { a m + b n ∣ m , n ∈ Z ∧ a m + b n > 0 } S=\{am+bn\mid m,n\in Z\ \land am+bn>0\} S={am+bn∣m,n∈Z ∧am+bn>0}
显然集合非空，选取 m m m和 n n n分别与 a a a和 b b b同号即可。
根据良序性，这个集合必然存在最小的元素，不妨设为 d = a s + b t d=as+bt d=as+bt，这里 s , t s,t s,t是集合取最小时确定的数。
根据定理内容， d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b)，我们证明这个即可。
根据Theorem 0.1，直接考虑 a a a除以 d d d，必有 a = d q + r , 0 ≤ r < d a=dq+r,0\le r<d a=dq+r,0≤r<d，如果 r ≠ 0 r\neq 0 r=0， r = a − d q = a − ( a s + b t ) q = a − a s q − b t q = a ( 1 − s q ) + b ( − t q ) ∈ S r=a-dq=a-(as+bt)q=a-asq-btq=a(1-sq)+b(-tq)\in S r=a−dq=a−(as+bt)q=a−asq−btq=a(1−sq)+b(−tq)∈S，这说明 d d d并非 S S S中最小的数（因为此时 r r r是 a a a和 b b b的线性组合），产生矛盾，因此必有 r = 0 → d ∣ a r=0\to d\mid a r=0→d∣a，同理， d ∣ b d\mid b d∣b，因此 d d d是 a , b a,b a,b的公约数。
假设存在比 d d d更大的公约数 d ′ d' d′，必有 ∃ h , k ∈ Z , s . t . a = d ′ h , b = d ′ k \exists h,k\in Z, \mathrm{s.t.}\ a=d'h,b=d'k ∃h,k∈Z,s.t. a=d′h,b=d′k，因此 d = a s + b t = a d ′ h + b d ′ k = d ′ ( a h + b k ) d=as+bt=ad'h+bd'k=d'(ah+bk) d=as+bt=ad′h+bd′k=d′(ah+bk)，显然 d ′ ∣ d d'\mid d d′∣d， d d d肯定是更大的数。推出矛盾，因此 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b)
a a a和 b b b互质等价于 ∃ s , t ∈ Z s . t . a s + b t = 1 \exists s,t\in Z\ \mathrm{s.t. }\ as+bt=1 ∃s,t∈Z s.t. as+bt=1
p ∣ a b → p ∣ a ∨ p ∣ b p\mid ab \to p\mid a\ \lor p\mid b p∣ab→p∣a ∨p∣b if p p p is a prime.
定理含义：质数如果是两个数乘积的约数，那么这个质数是这两个整数之一的约数。
证明：显然，分情况讨论下即可。
p ∣ a b ∧ p ∤ a → 1 = a s + p t → b = a s b + p t b p\mid ab\ \land\ p\nmid a\to 1=as+pt\to b=asb+ptb p∣ab ∧ p∤a→1=as+pt→b=asb+ptb， p p p是方程右侧的约数，自然是 b b b的约数
大于1的整数，要么是质数，要么是质数之积，且质因数分解方式唯一。
定理含义：算术基本定理，主要阐明，整数的质因数分解唯一。
证明：存在性的证明使用了强数学归纳法: 点击跳转 ;Euclid’s Lemma保证了分解的唯一性。
模是一种计数方法的抽象。例如，今天是星期3，23天后是星期几呢？只需要让23对7取余数，得2，所以答案是星期5.
模算术思想很简单，但在数学和计算机科学中很重要。
根据 Theorem 0.1 有 a = q n + r a=qn+r a=qn+r，我们记 a m o d n = r a\mod{n}=r amodn=r
有一些显而易见的结论值得列出：
尝试证明： x 2 − y 2 = 1002 x^2-y^2=1002 x2−y2=1002没有整数解。
证明：首先我们知道 1002 m o d 4 = 2 1002\mod{4}=2 1002mod4=2
对于任何整数，模4的结果只有0，1，2，3，而对于任何整数平方模4的结果，则只可能0，1，那很显然， x 2 − y 2 m o d 4 x^2-y^2\mod{4} x2−y2mod4的结果无论如何都不可能是2。
复数是具有形式 a + b i , a , b ∈ R , i = − 1 a+bi, a,b\in R,i=\sqrt{-1} a+bi,a,b∈R,i=−1的数。
极坐标表示 r ( cos ( θ ) + i sin ( θ ) ) r(\cos(\theta)+i\sin(\theta)) r(cos(θ)+isin(θ))
S S S is a set and a ∈ S a\in S a∈S，Suppose S S S has the property whenever some integer n ≥ a n\ge a n≥a belongs to S S S, then n + 1 n+1 n+1 also belong to S S S. Then, S S S contains every integer greater than or equal to a a a.
定理含义：说的是，如果集合 S S S有一个性质，即有一些大于等于 a a a的整数 n n n属于 S S S的话， n + 1 n+1 n+1必然也属于 S S S. 那么， S S S必然包含所有大于等于 a a a的整数。
S S S is a set and a ∈ S a\in S a∈S，Suppose S S S has the property that n ∈ S n\in S n∈S, when ∀ m ∈ S s . t . a ≤ m < n , m ∈ S \forall m\in S\ \mathrm{s.t.} \ a\le m<n,\mathrm{}\ m\in S ∀m∈S s.t. a≤m<n, m∈S .Then, S S S contains every integer greater than or equal to a a a.
定理含义：这里归纳仍然是需要两个条件，1. a ∈ S a\in S a∈S；2.如果假定 a ≤ m < n a\le m<n a≤m<n的所有 m m m都属于 S S S，可推出 n ∈ S n\in S n∈S
首先说明一下，上述两个定理的表述我是抄的书上的，更合适的说法应该不是自然数属于集合 S S S，而是自然数具有某种特定的性质。
第一种归纳法是我们常见的那种，即存在一个起始点 a a a具有性质 p p p，**我们假定 n n n也具有性质 p p p，可推出 n + 1 n+1 n+1也具有性质 p p p**时，就可以得出结论：任何大于等于 a a a的整数都具有性质 p p p
第二种归纳法也叫强归纳法，区别在第二个条件，可以使用 a a a到 n − 1 n-1 n−1的所有整数来推出 n n n，它假设的条件是更多的。
第二数学归纳法再某些情况下更好用，这里给出之前算术基本定理的证明：
约定，所有质数和质数之积的集合是 S S S
显然， 2 ∈ S 2\in S 2∈S，假定所有整数 ∀ k ∈ Z , s . t . 2 ≤ k < n → k ∈ S \forall k\in Z, \mathrm{s.t.}\ 2\le k<n\to k\in S ∀k∈Z,s.t. 2≤k<n→k∈S，对于 n n n来说，要么是质数属于 S S S，要么是合数可写成 a b , s . t . 1 < a < n ∧ 1 < b < n ab,\mathrm{s.t.}\ 1<a<n\ \land\ 1<b<n ab,s.t. 1<a<n ∧ 1<b<n，显然 a ∈ S ∧ b ∈ S a\in S\ \land\ b\in S a∈S ∧ b∈S，因此 n ∈ S n\in S n∈S
显然，通过这个证明，可以更深刻理解这两种归纳方式的别，强归纳法能在假设中把两个（甚至多个）变量 a a a和 b b b赋予性质 p p p，而第一种归纳方式仅假定了一个数。
给定任意面值5美元的硬币和面值8美元的硬币，找到这两种硬币最大的不可表示的总面值。
分析：很明显，题目就是求 5 5 5和 8 8 8的非负整数系数的所有线性组合所不能表达的最大数，用符号表示即是： max { Z − { 5 a + 8 b ∣ a , b ∈ Z s . t . a ≥ 0 , b ≥ 0 } } \max{\{Z-\{5a+8b\mid a,b\in Z\ \mathrm{s.t.}\ a\ge 0 ,b\ge 0\}\}} max{Z−{5a+8b∣a,b∈Z s.t. a≥0,b≥0}}
很容易可以从小到大列出可表达的面值：
5 = 5 × 1 + 8 × 0 5=5\times 1+8\times 0 5=5×1+8×0
8 = 5 × 0 + 8 × 1 8=5\times 0+8\times 1 8=5×0+8×1
10 = 5 × 2 + 8 × 0 10=5\times 2+8\times 0 10=5×2+8×0
13 = 5 × 1 + 8 × 1 13=5\times 1+8\times 1 13=5×1+8×1
⋯ \cdots ⋯
26 = 5 × 2 + 8 × 2 26=5\times 2+8\times 2 26=5×2+8×2
28 = 5 × 4 + 8 × 1 28=5\times 4+8\times 1 28=5×4+8×1
29 = 5 × 1 + 8 × 3 29=5\times 1+8\times 3 29=5×1+8×3
⋯ \cdots ⋯
39 = 5 × 3 + 8 × 3 39=5\times 3+8\times 3 39=5×3+8×3
40 = 5 × 8 + 8 × 0 40=5\times 8+8\times 0 40=5×8+8×0
似乎从 27 27 27后面所有数都有正确的表示，我们可以考虑能否证明所有大于 27 27 27的数都可以表示为 5 a + 8 b 5a+8b 5a+8b的形式。
约定下面的 a , b a,b a,b服从约束： a , b ∈ Z s . t . a ≥ 0 , b ≥ 0 a,b\in Z\ \mathrm{s.t.}\ a\ge 0,b\ge 0 a,b∈Z s.t. a≥0,b≥0
首先用第一数学归纳法：
显然 28 28 28可以表示为 5 a + 8 b 5a+8b 5a+8b的形式，那么假设大于 28 28 28的一个数 n = 5 a + 8 b n=5a+8b n=5a+8b，显然， a ≥ 3 ∨ b ≥ 3 a\ge 3\ \lor\ b\ge 3 a≥3 ∨ b≥3，因为如果不满足此条件，将有 n ≤ 28 n\le 28 n≤28
接下来我们有： n + 1 = 5 a + 8 b + ( − 3 ⋅ 5 + 2 ⋅ 8 ) = 5 ⋅ ( a − 3 ) + 8 ⋅ ( b + 2 ) n+1=5a+8b+(-3\cdot5+2\cdot 8)=5\cdot (a-3)+8\cdot (b+2) n+1=5a+8b+(−3⋅5+2⋅8)=5⋅(a−3)+8⋅(b+2)
n + 1 = 5 a + 8 b + ( 5 ⋅ 5 − 3 ⋅ 8 ) = 5 ⋅ ( a + 5 ) + 8 ⋅ ( b − 3 ) n+1=5a+8b+(5\cdot5-3\cdot 8)=5\cdot (a+5)+8\cdot (b-3) n+1=5a+8b+(5⋅5−3⋅8)=5⋅(a+5)+8⋅(b−3)
显然，递推可以继续，QED
然后使用第二数学归纳法：
首先， 28 28 28满足条件，我们很容易验证 28 , 29 , 30 , 31 , 32 28,29,30,31,32 28,29,30,31,32满足条件，那么对于 n > 32 n>32 n>32，我们假定所有 28 ≤ k < n 28\le k< n 28≤k<n满足条件，现在要证明 n n n满足条件，很简单，由于 n − 5 n-5 n−5满足， n n n自然满足（只需要把 a a a系数增加 1 1 1就是 n n n的表示）。QED
事物的关系是复杂的，也取决于我们看待问题的角度，两件事物在一种角度下是完全不同的，但可能在另一种情况下是等价的。一个典型的例子是3和8当然是不同的，但在模5运算下确实相同的。数学中等价关系用于精确地区分各种等价和差异。
An equivalence relation on a set S S S is a set R R R of ordered pairs of elements of S S S such that
- ( a , a ) ∈ R ∀ a ∈ S (a,a)\in R\ \forall\ a\in S (a,a)∈R ∀ a∈S
- ( a , b ) ∈ R → ( b , a ) ∈ R (a,b)\in R\to (b,a)\in R (a,b)∈R→(b,a)∈R
- ( a , b ) ∈ R ∧ ( b , c ) ∈ R → ( a , c ) ∈ R (a,b)\in R\ \land\ (b,c)\in R\to(a,c)\in R (a,b)∈R ∧ (b,c)∈R→(a,c)∈R
定义理解：等价关系需要对一个集合声明和定义（on a set S S S），它本身是一个有序二元对集合 R R R，二元对中的每个元素都是 S S S的元素。且等价关系满足反身性，对称性和传递性。
如果 S S S是定义等价关系的集合， R R R表示等价关系， a , b ∈ S a,b\in S a,b∈S
这里仅列出几个重要的例子：
模 n n n同余：
n n n是正整数， a , b ∈ Z a,b\in Z a,b∈Z， a ∼ b i f a m o d n = b m o d n a\sim b\ \mathrm{if}\ a\mod{n}=b\mod{n} a∼b if amodn=bmodn，模 n n n同余定义了一种等价关系，等价类可以表示为 [ a ] = { a + k n ∣ k ∈ Z } [a]=\{a+kn\mid k\in Z\} [a]={a+kn∣k∈Z}。这个等价关系很容易验证满足三条件。
S = { ( a , b ) ∣ a , b ∈ Z , b ≠ 0 } S=\{(a,b)\mid a,b\in Z,b\neq 0\} S={(a,b)∣a,b∈Z,b=0}，在 S S S上定义等价关系： ( a , b ) ∼ ( c , d ) i f a d = b c (a,b)\sim (c,d)\ \mathrm{if}\ ad=bc (a,b)∼(c,d) if ad=bc，这个等价关系的动机来自于分数，实际上表示分数相等 a / b = c / d a/b=c/d a/b=c/d。
集合的划分指的是集合 S S S分为几个不相交的，并集为 S S S的子集。
定义划分的目的是为了引入等价类的划分方式。
集合 S S S上定义的一个等价关系的等价类构成集合 S S S的一个划分。反之也成立，对于集合 S S S的任何划分，都可以据此定义一个等价关系。
定理理解：这个定理实际上说明等价关系的定义和集合划分是等效的操作。
证明：这个定理的反之这里就不作证明了，因为可以用比较无脑的方式给出，直接定义等价关系就是属于某个划分后的子集就行。
对于等价关系如何形成划分的证明，要证明等价类无交集且并集是 S S S。
首先等价类肯定无交集，因为传递性导致如果两个等价类有交集，这两个等价类就是一个等价类。
所有等价类的并集是 S S S就更好证明了，对所有元素各自求一个等价类，这些等价类必然包含这些元素，那么他们的并必然是 S S S。
接下来介绍一下函数，函数在数学众多领域中都是至关重要的，各种关于函数的记号却有略微差别，这里约定好关于函数的定义和记号。
A function (or mapping) ϕ \phi ϕ for a set A A A to a set B B B is a rule that assigns to each element a a a of A A A exactly one element b b b of B B B. A A A is called the domain of ϕ \phi ϕ, and B B B is called a range of ϕ \phi ϕ. if ϕ \phi ϕ assigns b b b to a a a, b b b is called the image of a a a under ϕ \phi ϕ. The subset of B B B comprising all the images of elements of A A A is called the image of A A A under ϕ \phi ϕ
定义理解：
两集合映射的表示：
ϕ
:
A
→
B
\phi:A\to B
ϕ:A→B
元素间映射的表示：
ϕ
:
a
→
b
\phi:a\to b
ϕ:a→b or
ϕ
(
a
)
=
b
\phi(a)=b
ϕ(a)=b
Let ϕ : A → B \phi : A\to B ϕ:A→B and φ : B → C \varphi :B\to C φ:B→C. The composition φ ϕ \varphi\phi φϕ is a mapping from A A A to C C C.
We denote that ( f ∘ g ) ( x ) = f ( g ( x ) ) (f\circ g)(x)=f(g(x)) (f∘g)(x)=f(g(x))
约定讨论函数 ϕ : A → B \phi :A\to B ϕ:A→B
理解：这两种映射可以翻译为“一一的”和“到上的”，实际上对应的是单射和满射。“一一的”代表像相同则原像相等，即不能有多个原像映射到同一个像。“到上的”即集合 B B B中所有元素都是像，也即是 A A A的像等于值域。