11/05 考前完整版：定義、定理、證明與精確用語

先讀這份，再抄 a4.html。
用瀏覽器讀：complete.html（MathJax 已本地化）。
這份是「讀懂版」：把定義的量化寫法、定理的假設、證明的開頭與結尾寫清楚。A4 是「考試版」：只留索引、骨架與易錯。

0. 怎麼用這份

1. 先逐節讀定義與定理，嘴巴講一次「假設是什麼、結論是什麼」。
2. 證明不要背全文，背「第一行」與「最後一行」；中間用公理補。
3. 讀完一節，回頭看 A4 對應欄位；如果 A4 那行你看不懂，代表這節沒讀通。
4. 考前只看 A4，不再開新題。

1. 自然數與整數（Natural Numbers & Integers）

1.1 Peano 公理（Peano Axioms）

以 \(1\) 為起始元素：

1. \(1\in\mathbb{N}\)。
2. 對任意 \(n\in\mathbb{N}\)，後繼 \(S(n)\in\mathbb{N}\)。
3. 對任意 \(n\in\mathbb{N}\)，\(S(n)\neq1\)。
4. 對任意 \(m,n\in\mathbb{N}\)，\(S(m)=S(n)\Rightarrow m=n\)。
5. 歸納公理：若 \(A\subseteq\mathbb{N}\) 滿足 \(1\in A\)，且 \(n\in A\Rightarrow S(n)\in A\)，則 \(A=\mathbb{N}\)。

加法與乘法不是預先給定的，而是用 \(S\) 遞迴定義。考試若問「為什麼需要 Peano」，答案是：它把自然數的「起始、後繼、不會繞回、不會重複、可以歸納」說清楚。

1.2 等價關係與 Z 的建構（Equivalence Relations & Construction of Z）

等價關係（equivalence relation）：集合 \(X\) 上的關係 \(\sim\) 滿足

• 自反：\(\forall a\in X,\ a\sim a\)。
• 對稱：\(\forall a,b\in X,\ a\sim b\Rightarrow b\sim a\)。
• 傳遞：\(\forall a,b,c\in X,\ a\sim b,\ b\sim c\Rightarrow a\sim c\)。

等價類（equivalence class）：\([a]=\{x\in X\mid x\sim a\}\)。商集合（quotient set）：\(X/\sim=\{[a]\mid a\in X\}\)。

整數的建構（construction of Z）：在 \(\mathbb{N}\times\mathbb{N}\) 上定義

\[ (a,b)\sim(c,d)\iff a+d=b+c. \]

則 \(\mathbb{Z}=(\mathbb{N}\times\mathbb{N})/\sim\)，而 \([(a,b)]\) 代表 \(a-b\)。

注意 起始元素約定 若 \(\mathbb{N}=\{1,2,3,\dots\}\)，自然數 \(n\) 的嵌入是 \(n\mapsto[(n+1,1)]\)；若講義用 \(\mathbb{N}=\{0,1,2,\dots\}\)，則是 \(n\mapsto[(n,1)]\)。考試以講義的約定為準，不要混用。

加法良定義（well-defined addition）：定義 \([(a,b)]+[(c,d)]=[(a+c,b+d)]\)。要證它與代表元無關：

設 \((a,b)\sim(a',b')\)、\((c,d)\sim(c',d')\)，即

\[ a+b'=b+a',\qquad c+d'=d+c'. \]

兩式相加並整理：

\[ (a+c)+(b'+d')=(b+d)+(a'+c'), \]

所以 \((a+c,b+d)\sim(a'+c',b'+d')\)。這就是「well-defined」的標準寫法：先設兩組代表元，再證結果落在同一個等價類。

乘法：\([(a,b)]\cdot[(c,d)]=[(ac+bd,ad+bc)]\)，良定義的證法同理，只是展開較長。

1.3 良序原理與歸納法（Well-Ordering Principle & Induction）

良序原理（WOP）：\(\mathbb{N}\) 的每個非空子集都有最小元素。

它與歸納公理等價。很多存在性證明用它：先取一個非空集合，取最小元素，再用「更小」制造矛盾。除法原理的存在性、循環群子群定理都用到它。

1.4 除法原理、gcd、Bézout（Division Algorithm, gcd, Bézout）

Division Algorithm：對任意 \(a\in\mathbb{Z}\)、\(b\in\mathbb{Z}\) 且 \(b\gt 0\)，存在唯一 \(q,r\in\mathbb{Z}\) 使

\[ a=bq+r,\qquad 0\le r\lt b. \]

gcd（greatest common divisor）：\(d=\gcd(a,b)\) 是同時整除 \(a,b\) 的最大正整數。等價地：\(d\mid a\)、\(d\mid b\)，且任何公因數都整除 \(d\)。

Euclidean Algorithm（輾轉相除法）：

\[ \gcd(a,b)=\gcd(b,a\bmod b). \]

一直做到餘數 \(0\)，最後的非零餘數就是 gcd。

Bézout's Identity（貝祖等式）：若 \(d=\gcd(a,b)\)，則存在 \(x,y\in\mathbb{Z}\) 使

\[ ax+by=d. \]

它是「乘法反元素存在 ⇔ gcd \(=1\)」的根據：若 \(\gcd(a,n)=1\)，則 \(ax+ny=1\)，取模 \(n\) 得 \(ax\equiv1\pmod{n}\)。

Euclid's Lemma（歐幾里得引理）：若 \(p\) 是質數且 \(p\mid ab\)，則 \(p\mid a\) 或 \(p\mid b\)。

Fundamental Theorem of Arithmetic（算術基本定理）：每個 \(n\gt 1\) 都可以唯一分解成質數的乘積（不計因數順序）。

例：\(\gcd(252,198)\)。

\[ 252=1\cdot198+54,\quad 198=3\cdot54+36,\quad 54=1\cdot36+18, \]

故 \(\gcd=18\)。回代：

\[ 18=54-36=54-(198-3\cdot54)=4\cdot54-198=4\cdot252-5\cdot198. \]

2. 同餘與 Z_n（Congruences & Modular Arithmetic）

2.1 同餘、剩餘類、Z_n（Congruence, Residue Classes, Z_n）

同餘（congruence）：\(a\equiv b\pmod{n}\) 定義為 \(n\mid(a-b)\)。

剩餘類（residue class）：

\[ [a]=\{a+kn\mid k\in\mathbb{Z}\}. \]

\(\mathbb{Z}_n\)：

\[ \mathbb{Z}_n=\{[0],[1],\dots,[n-1]\}. \]

它是商集合 \((\mathbb{Z}/\equiv_n)\)；元素是「等價類」，不是單一數字。

運算：

\[ [a]+[b]=[a+b],\qquad [a][b]=[ab]. \]

良定義（加法）：若 \(a\equiv a'\pmod{n}\)、\(b\equiv b'\pmod{n}\)，則

\[ (a+b)-(a'+b')=(a-a')+(b-b') \]

是 \(n\) 的倍數，所以 \(a+b\equiv a'+b'\pmod{n}\)。

良定義（乘法）：

\[ ab-a'b'=a(b-b')+(a-a')b' \]

也是 \(n\) 的倍數。

2.2 Unit 與 zero divisor（Units & Zero Divisors）

• \([a]\) 是 unit（可逆元）⇔ 存在 \([b]\) 使 \([a][b]=[1]\) ⇔ \(\gcd(a,n)=1\)。
• \([a]\) 是 zero divisor ⇔ \([a]\neq[0]\)，且存在 \([b]\neq[0]\) 使 \([a][b]=[0]\)。在 \(\mathbb{Z}_n\) 中，通常對應 \(\gcd(a,n)\gt 1\)（\([0]\) 除外）。

例：\(\mathbb{Z}_6\) 中 unit 是 \([1],[5]\)；zero divisor 是 \([2],[3],[4]\)。

2.3 消去律（Cancellation Law）

定理（可以消）／Cancellation Law：若 \(\gcd(c,n)=1\) 且 \(ac\equiv bc\pmod{n}\)，則 \(a\equiv b\pmod{n}\)。

證明：\(n\mid c(a-b)\)。因為 \(\gcd(c,n)=1\)，由 Euclid's Lemma（或 Bézout）得 \(n\mid(a-b)\)，即 \(a\equiv b\pmod{n}\)。

一般情形：若 \(d=\gcd(c,n)\)，則

\[ ac\equiv bc\pmod{n}\Rightarrow a\equiv b\pmod{n/d}. \]

證明：寫 \(c=dc'\)、\(n=dn'\)，則 \(\gcd(c',n')=1\)，且 \(n'\mid c'(a-b)\)，故 \(n'\mid(a-b)\)。

反例：\(2\cdot0\equiv2\cdot2\pmod4\)，但 \(0\not\equiv2\pmod4\)；因為 \(\gcd(2,4)=2\)，只能推 \(0\equiv2\pmod2\)。

2.4 線性同餘（Linear Congruences）

定理：\(ax\equiv b\pmod{n}\)，令 \(d=\gcd(a,n)\)。

• 有解 ⇔ \(d\mid b\)。
• 若有解，則在模 \(n\) 下恰有 \(d\) 個解：

\[ x\equiv x_0+k\frac{n}{d}\pmod{n},\qquad k=0,1,\dots,d-1. \]

證明骨架：\(d\mid b\) 時，寫 \(b=db'\)、\(a=da'\)、\(n=dn'\)，則 \(\gcd(a',n')=1\)，方程化為 \(a'x\equiv b'\pmod{n'}\)，有唯一解 \(x_0\)；再加上 \(k(n/d)\) 得到 \(d\) 個解。

例：\(6x\equiv9\pmod{15}\)，\(d=3\)。除以 \(3\)：

\[ 2x\equiv3\pmod5. \]

\(2^{-1}\equiv3\pmod5\)，所以 \(x\equiv9\equiv4\pmod5\)，即

\[ x\equiv4,9,14\pmod{15}. \]

2.5 Fermat、Euler、Wilson、CRT（Fermat, Euler, Wilson, CRT）

Fermat's Little Theorem：\(p\) 質數、\(p\nmid a\)，則

\[ a^{p-1}\equiv1\pmod{p}. \]

等價地，對所有 \(a\)，\(a^p\equiv a\pmod{p}\)。

Euler's Theorem：若 \(\gcd(a,n)=1\)，則

\[ a^{\phi(n)}\equiv1\pmod{n}. \]

Wilson's Theorem：對 \(n\gt 1\)，

\[ n\text{ 為質數}\iff(n-1)!\equiv-1\pmod{n}. \]

CRT（兩兩互質版）：若 \(m_1,\dots,m_k\) 兩兩互質，則

\[ x\equiv a_i\pmod{m_i}\quad(i=1,\dots,k) \]

在模 \(M=\prod m_i\) 下有唯一解。

CRT（一般條件）：兩條方程 \(x\equiv a_1\pmod{m_1}\)、\(x\equiv a_2\pmod{m_2}\) 有解 ⇔

\[ \gcd(m_1,m_2)\mid(a_1-a_2). \]

若有解，則在模 \(\operatorname{lcm}(m_1,m_2)\) 下唯一。

注意 週期不是最小階 \(a^{\phi(n)}\equiv1\) 只說 \(\phi(n)\) 是一個「保證的週期」，不是最小週期。真正的最小階（order）整除 \(\phi(n)\)。Fermat 的 \(p-1\) 也一樣；例如 \(2^6\equiv1\pmod7\)，但 \(2\) 的階是 \(3\)。

例：\(3^{103}\bmod100\)。

\[ \phi(100)=40,\qquad 103=2\cdot40+23, \]

所以

\[ 3^{103}\equiv3^{23}\equiv27\pmod{100}. \]

3. 群與子群（Groups & Subgroups）

3.1 二元運算與群公理（Binary Operations & Group Axioms）

二元運算（binary operation）：映射

\[ *:G\times G\to G. \]

說一個運算是二元運算，要確認：每個 \((a,b)\) 都有定義、結果唯一、且結果落在 \(G\) 裡（封閉）。

群（group）：\((G,*)\) 滿足

• G1 封閉：\(\forall a,b\in G,\ a*b\in G\)。
• G2 結合：\(\forall a,b,c\in G,\ (a*b)*c=a*(b*c)\)。
• G3 單位元：\(\exists e\in G\) 使 \(\forall x\in G,\ e*x=x*e=x\)。
• G4 逆元：\(\forall a\in G,\ \exists a^{-1}\in G\) 使 \(a*a^{-1}=a^{-1}*a=e\)。

Abelian（交換群）：群，且 \(\forall a,b\in G,\ ab=ba\)。

補充 課本與講義的編號 Fraleigh 課本用 \(\mathcal{G}_1\)（結合）、\(\mathcal{G}_2\)（單位）、\(\mathcal{G}_3\)（逆元），封閉含在二元運算的定義裡。講義用 G1（封閉）、G2（結合）、G3（單位）、G4（逆元）。答題時先把公理寫出來，不要只寫編號。

經典例子：

3.2 由公理推得的五個直接結論（Direct Consequences）

1. 單位元唯一

設 \(e,e'\) 都是單位元。則

\[ e=e*e'=e'. \]

2. 逆元唯一

設 \(b,c\) 都是 \(a\) 的逆元。則

\[ b=b*e=b*(a*c)=(b*a)*c=e*c=c. \]

3. 倒置律

\[ (ab)(b^{-1}a^{-1})=a(bb^{-1})a^{-1}=aa^{-1}=e. \]

另一邊同理，故 \((ab)^{-1}=b^{-1}a^{-1}\)。

4. 消去律

若 \(ab=ac\)，左乘 \(a^{-1}\)：

\[ (a^{-1}a)b=(a^{-1}a)c\Rightarrow eb=ec\Rightarrow b=c. \]

5. 線性方程的唯一解

\(ax=b\) 的唯一解是 \(x=a^{-1}b\)；\(ya=b\) 的唯一解是 \(y=ba^{-1}\)。非交換群左右不同。

注意 精確用語 不要寫「兩邊同除以 \(a\)」，要寫「兩邊左乘 \(a^{-1}\)」。不要寫「把 \(a\) 消掉」，要寫「由消去律」。每一步要指出用了 G2 結合律、G3 單位元、G4 逆元，或哪個已證結論。

3.3 子群與子群判定法（Subgroups & Subgroup Tests）

子群（subgroup）：\(H\le G\) 表示 \(H\subseteq G\)、\(H\neq\varnothing\)，且 \(H\) 在 \(G\) 的限制運算下自身構成群。

三條件：

1. 封閉：\(\forall a,b\in H,\ ab\in H\)。
2. 單位元：\(e\in H\)。
3. 逆元：\(\forall a\in H,\ a^{-1}\in H\)。

結合律自動繼承自 \(G\)，不必重新證明。

一步子群判定法（one-step subgroup test）：\(H\le G\) ⇔

\[ H\neq\varnothing,\qquad \forall a,b\in H,\ ab^{-1}\in H. \]

證明：

• 取 \(x\in H\)，則 \(xx^{-1}=e\in H\)。
• 取 \(a=e,b=x\)，則 \(ex^{-1}=x^{-1}\in H\)。
• 取 \(a=x,b=y^{-1}\)，則 \(x(y^{-1})^{-1}=xy\in H\)。
• 結合律繼承自 \(G\)，故 \(H\le G\)。

有限子群判定法（finite subgroup test）：若 \(H\) 是 \(G\) 的有限非空子集，且對乘法封閉，則 \(H\le G\)。

證明骨架：對 \(a\in H\)，序列 \(a,a^2,a^3,\dots\) 都在 \(H\)。因 \(H\) 有限，存在 \(m\gt n\) 使 \(a^m=a^n\)，故 \(a^{m-n}=e\in H\)，且 \(a^{-1}=a^{m-n-1}\in H\)。

反例：\(\mathbb{Z}^+=\{1,2,3,\dots\}\) 在加法下封閉，但不是 \(\mathbb{Z}\) 的子群——沒有 \(0\)，也沒有負數逆元。它是無限子集，所以不能只用封閉性判定。

同構（isomorphism）：雙射 \(\phi:G\to G'\) 滿足

\[ \phi(ab)=\phi(a)\phi(b). \]

同構的群有相同的群論性質（階、交換性、元素階等）。

4. 循環群（Cyclic Groups）

4.1 定義與階（Definition & Order）

循環群（cyclic group）：存在 \(a\in G\) 使

\[ G=\langle a\rangle=\{a^k\mid k\in\mathbb{Z}\}. \]

群的階（order of a group）：\(|G|\) 是 \(G\) 的元素個數。

元素的階（order of an element）：

\[ \lvert a\rvert=\min\{n\in\mathbb{Z}_{\gt 0}\mid a^n=e\}. \]

若不存在這樣的正整數，稱 \(a\) 有無限階。並且

\[ \lvert a\rvert=\lvert\langle a\rangle\rvert. \]

例：\(\mathbb{Z}_{12}\) 中 \(|\bar4|=3\)，因為

\[ \bar4+\bar4+\bar4=\bar{12}=\bar0, \]

而 \(\bar4,\bar8\) 都不是 \(\bar0\)。

4.2 循環群的基本性質（Basic Properties）

循環 ⇒ Abelian：若 \(G=\langle a\rangle\)，則任意 \(g_1=a^r\)、\(g_2=a^s\)，故

\[ g_1g_2=a^{r+s}=a^{s+r}=g_2g_1. \]

反之不成立：Klein \(V\) 是 Abelian，但每個非單位元的階都是 \(2\)，生成不出 \(4\) 階群，所以不是循環群。

循環群的子群仍循環：設 \(G=\langle a\rangle\)，\(H\le G\)。若 \(H=\{e\}\)，顯然。否則取 \(H\) 中最小正指數 \(m\)（良序原理），證明 \(H=\langle a^m\rangle\)：任取 \(a^n\in H\)，用除法原理寫 \(n=mq+r\)，\(0\le r\lt m\)，則 \(a^r\in H\)；由 \(m\) 的最小性，\(r=0\)。

4.3 階的公式、生成元、子群結構（Order Formula, Generators, Subgroup Structure）

設 \(G=\langle a\rangle\) 且 \(|a|=n\)。

1. 次方的階：

\[ \lvert a^s\rvert=\frac{n}{\gcd(n,s)}. \]

2. 生成元：\(a^s\) 生成 \(G\) ⇔ \(\gcd(s,n)=1\)。生成元共有 \(\phi(n)\) 個。

3. 子群結構：對每個 \(d\mid n\)，恰有一個 \(d\) 階子群，由 \(a^{n/d}\) 生成。

4. 分類：無限循環群同構於 \((\mathbb{Z},+)\)；\(n\) 階循環群同構於 \((\mathbb{Z}_n,+)\)。

例：\(\mathbb{Z}_{18}\)。生成元是 \(\bar1,\bar5,\bar7,\overline{11},\overline{13},\overline{17}\)，共 \(\phi(18)=6\) 個。子群階數為 \(1,2,3,6,9,18\)。

注意 公式的前提 \(|a^s|=n/\gcd(n,s)\) 的前提是 \(|a|=n\)。如果 \(a\) 不是 \(G\) 的生成元，\(n\) 不能代 \(|G|\)；要用 \(|a|\)。

5. 生成集與 Cayley Digraph（Generating Sets & Cayley Digraphs）

5.1 生成集（Generating Sets）

由子集生成的子群（subgroup generated by a subset）：\(\langle S\rangle\) 是包含 \(S\) 的最小子群，也等於 \(S\) 中元素及其逆元的所有有限乘積。

有限生成群（finitely generated group）：存在有限子集 \(S\) 使 \(G=\langle S\rangle\)。

5.2 Cayley digraph（Cayley Digraphs）

給定群 \(G\) 與生成集 \(S\)。

• 頂點（vertex）：每個頂點對應 \(G\) 的一個元素。
• 弧（arc）：對每個 \(g\in S\)，從 \(x\) 畫一條弧到 \(xg\)，標記 \(g\)。這是右乘。
• 自逆元素（self-inverse element）：若 \(g=g^{-1}\)（即 \(g^2=e\)），通常畫成無向邊，不畫箭頭。

四大性質：

1. 連通：\(S\) 生成 \(G\)，所以任兩點間有路徑。
2. 出入度：對每個 \(g\in S\)，每個頂點恰有一條 \(g\)-出邊與一條 \(g\)-入邊。
3. 邊的唯一性：給定 \(x\) 與 \(g\)，\(xg\) 唯一，所以同型邊不重複。
4. 平移一致性：從任一點走同一字詞，到達的點是原點的右乘平移。

例：

• \(\mathbb{Z}_8\) 用 \(S=\{1\}\)：有向 8-cycle。
• Klein \(V\) 用 \(S=\{a,b\}\)：\(a,b\) 都自逆，畫出 4-cycle。
• \(D_4\) 用 \(S=\{r,s\}\)：\(r\) 是 \(90^\circ\) 旋轉（\(r^4=e\)，不是自逆），\(s\) 是反射（\(s^2=e\)，自逆）。每個頂點一條 \(r\)-出弧與一條 \(s\)-邊。

5.3 D3 的 6×6 Cayley table（D3 Cayley Table, ρ/τ version）

老師上課用正三角形，把六個對稱寫成

\[ \rho_0,\rho_1,\rho_2,\tau_1,\tau_2,\tau_3, \]

其中 \(\rho_0\) 是恆等，\(\rho_1\) 是旋轉 \(120^\circ\)，\(\rho_2\) 是旋轉 \(240^\circ\)；\(\tau_1,\tau_2,\tau_3\) 是三個反射。用置換的兩行記法：

\[ \rho_0=\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix},\quad \rho_1=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix},\quad \rho_2=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}, \]

\[ \tau_1=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix},\quad \tau_2=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix},\quad \tau_3=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}. \]

約定：下表「列（Row）＝先做的運算，行（Column）＝後做的運算」，表格值＝先列後行。也就是第 \(x\) 列、第 \(y\) 行的值是「先 \(x\) 再 \(y\)」。

檢查：

• 每一列、每一行都是六個元素的排列（封閉）。
• 第一列與第一行都是 \(\rho_0\)（單位元）。
• 每個元素在表中恰出現一次 \(\rho_0\)（逆元）：

\[ \rho_0^{-1}=\rho_0,\quad \rho_1^{-1}=\rho_2,\quad \rho_2^{-1}=\rho_1,\quad \tau_i^{-1}=\tau_i\ (i=1,2,3). \]

• 非 Abelian：\(\tau_1\rho_1=\tau_3\)，但 \(\rho_1\tau_1=\tau_2\)，兩者不相等。
• 若你用 \(e,r,r^2,s,sr,sr^2\) 的標準表，對應關係可取 \(e=\rho_0\)、\(r=\rho_1\)、\(r^2=\rho_2\)、\(s=\tau_1\)、\(sr=\tau_2\)、\(sr^2=\tau_3\)；考試時選一種標籤，從頭用到尾，不要中途混用。

注意 表格會轉置 若你採用課本慣例「乘積 \(ab\) 表示先 \(b\) 後 \(a\)」，同一組元素的 Cayley table 會是這張表的轉置。考試時先在表頭寫清楚「列先、行後」或「行先、列後」，不要把兩張表混用。

6. 證明的精確用語（Precise Proof Language）

這一節是「把話說對」的清單。考試寫證明時，寧可短，但每個量詞與方向要正確。

6.1 量詞與存在性（Quantifiers & Existence）

6.2 群證明的固定句式（Proof Templates）

• 要證 \(H\le G\)：先寫「\(H\neq\varnothing\)」，再「任取 \(a,b\in H\)」，證「\(ab^{-1}\in H\)」，最後「結合律繼承自 \(G\)」。
• 要證唯一：先「設 \(x,y\) 都滿足…」，再證「\(x=y\)」。
• 要證 \(ax=b\)：寫「兩邊左乘 \(a^{-1}\)」，不要寫「同除」。
• 要證 \(ya=b\)：寫「兩邊右乘 \(a^{-1}\)」。
• 要證 well-defined：先「設兩組代表元…」，再證「結果在同一個等價類」。
• 要證循環群子群：用良序原理取最小正指數，再用除法原理。
• 要證有限子群：先寫「\(H\) 有限非空」，再證封閉；不要對無限子集使用。

6.3 常見錯句（Common Wrong Phrases）

7. 三個作業證明（Three Homework Proofs）

7.1 最大公因數存在且唯一（Existence & Uniqueness of gcd）

定理：設 \(a,b\in\mathbb{Z}\) 不全為 \(0\)。則存在唯一的正整數 \(d\) 滿足：

1. \(d\mid a\) 且 \(d\mid b\)；
2. 若 \(c\mid a\) 且 \(c\mid b\)，則 \(c\mid d\)。

稱 \(d=\gcd(a,b)\)。

存在性：考慮

\[ S=\{ax+by\mid x,y\in\mathbb{Z},\ ax+by\gt 0\}. \]

• \(S\neq\varnothing\)：若 \(a\neq0\)，則 \(|a|\in S\)；若 \(b\neq0\)，則 \(|b|\in S\)。
• 由良序原理，取 \(d=ax_0+by_0\) 為 \(S\) 的最小元。
• 用除法原理寫 \(a=dq+r\)，\(0\le r\lt d\)。則

\[ r=a-dq=a(1-x_0q)+b(-y_0q). \]

若 \(r\gt 0\)，則 \(r\in S\) 且 \(r\lt d\)，與 \(d\) 的最小性矛盾；故 \(r=0\)，即 \(d\mid a\)。同理 \(d\mid b\)。

• 若 \(c\mid a\)、\(c\mid b\)，則 \(c\mid(ax_0+by_0)=d\)。故 \(d\) 是最大公因數。

唯一性：設 \(d_1,d_2\) 都滿足定義。把 \(d_2\) 看成公因數、\(d_1\) 看成 gcd，得 \(d_2\mid d_1\)；反之得 \(d_1\mid d_2\)。兩者都是正整數，故 \(d_1=d_2\)。

注意 邊界 若 \(a=b=0\)，\(\gcd\) 未定義（或約定為 \(0\)）。考試先寫「\(a,b\) 不全為 \(0\)」，並取 \(d\gt 0\)。

7.2 Division Algorithm（帶餘除法）

定理：對任意 \(a\in\mathbb{Z}\)、\(b\in\mathbb{Z}\) 且 \(b\gt 0\)，存在唯一 \(q,r\in\mathbb{Z}\) 使

\[ a=bq+r,\qquad 0\le r\lt b. \]

存在性：考慮

\[ S=\{a-bk\mid k\in\mathbb{Z},\ a-bk\ge0\}. \]

• 若 \(a\ge0\)，取 \(k=0\)，則 \(a\in S\)。
• 若 \(a\lt 0\)，取 \(k=a\)。因為 \(b\ge1\)，

\[ a-ba=a(1-b)\ge0, \]

故 \(a-ba\in S\)。因此 \(S\neq\varnothing\)。

由良序原理，取 \(r=a-bq\) 為 \(S\) 的最小元。若 \(r\ge b\)，則

\[ r-b=a-b(q+1)\in S \]

且 \(r-b\lt r\)，與 \(r\) 的最小性矛盾。故 \(r\lt b\)。於是 \(a=bq+r\)、\(0\le r\lt b\)。

唯一性：設 \(a=bq+r=bq'+r'\)，且 \(0\le r,r'\lt b\)。相減得

\[ b(q-q')=r'-r. \]

另一方面，\(-b\lt r'-r\lt b\)，即 \(|r'-r|\lt b\)。一個絕對值嚴格小於 \(b\) 的 \(b\) 的倍數只能是 \(0\)，故 \(r'=r\)。代回得 \(b(q-q')=0\)；因為 \(b\gt 0\)，所以 \(q=q'\)。

注意 邊界 定理要求 \(b\gt 0\)。若 \(b\lt 0\)，先換成 \(|b|\)；若 \(b=0\)，除法無定義。

7.3 算術基本定理（Fundamental Theorem of Arithmetic）

定理：每個整數 \(n\gt 1\) 都可寫成質數的乘積；若不計順序，分解唯一。

存在性（強歸納法）：

• \(n=2\) 是質數，成立。
• 設所有 \(2\le k\lt n\) 都可分解。若 \(n\) 是質數，本身即分解；若 \(n\) 是合數，寫 \(n=ab\)，其中 \(1\lt a,b\lt n\)。由歸納假設，\(a,b\) 都可分解成質數乘積；把它們接起來，就是 \(n\) 的分解。

Euclid's Lemma：若 \(p\) 是質數且 \(p\mid ab\)，則 \(p\mid a\) 或 \(p\mid b\)。

推廣：若 \(p\) 是質數且 \(p\mid q_1q_2\cdots q_s\)，其中 \(q_j\) 都是質數，則 \(p=q_j\) 對某個 \(j\) 成立。證明：\(s=1\) 時，\(p\mid q_1\) 且 \(q_1\) 質數，故 \(p=q_1\)。設 \(s-1\) 成立；對 \(s\)，由 Euclid's Lemma，\(p\mid q_1\cdots q_{s-1}\) 或 \(p\mid q_s\)。前者用歸納假設，後者因 \(q_s\) 質數得 \(p=q_s\)。

唯一性（強歸納法）：

• \(n=2\) 唯一。
• 設 \(n\) 有兩種分解，將質數按非遞減順序排列：

\[ n=p_1p_2\cdots p_r=q_1q_2\cdots q_s. \]

因為 \(p_1\mid q_1\cdots q_s\)，由推廣得 \(p_1=q_j\) 對某個 \(j\)。由於 \(q_1\) 是最小的，\(p_1=q_j\ge q_1\)。同理 \(q_1\ge p_1\)，故 \(p_1=q_1\)。

由整數消去律，兩邊消去 \(p_1\)：

\[ n'=\frac{n}{p_1}=p_2\cdots p_r=q_2\cdots q_s. \]

若 \(n'=1\)，則 \(r=s=1\)；若 \(n'\gt 1\)，則 \(n'\lt n\)，由歸納假設，\(n'\) 的分解唯一，故 \(r=s\) 且 \(p_i=q_i\)（\(i\ge2\)）。結合 \(p_1=q_1\)，得 \(r=s\) 且所有 \(p_i=q_i\)。

次數版本：把相同質數合併成 \(n=p_1^{a_1}\cdots p_k^{a_k}\)；由上述唯一性，質數種類與各質數的次數都唯一。

7.4 NotebookLM 寫法檢查（Review）

結論：這三個證明的骨架都可以用；照本文版本寫，補上假設、量詞與「用了哪個定理」，就不會被扣分。

7.5 proof.pdf 的表格核對（Table Check）

你給的 proof.pdf 有五張表；我逐格看過（OCR 層不可靠，以下按手寫內容判斷）：

• 6×6 表：36 格全部正確。以「列先、行後」讀，和 \(S_3\) 的合成表完全一致；沒有抄錯。
• 左上角：你寫的看起來像 0，但這裡應該是合成符號 \(\circ\)；抄的時候寫 \(\circ\) 或 \(\cdot\)，不要寫成零。
• 四張 3×3 表：\(C_3\) 旋轉表、\((\mathbb{Z}_3,+)\) 表、三次單位根表、\(120^\circ/240^\circ\) 矩陣表，內容都正確。
• 置換標籤：\(\rho_0\) 是恆等，\(\rho_1=(123)\)，\(\rho_2=(132)\)；\(\tau_1=(23)\)，\(\tau_2=(13)\)，\(\tau_3=(12)\)，也正確。

所以這份 PDF 的表格不用重抄；只要把左上角的 0 改成 \(\circ\)，並在表頭註明「列先、行後」即可。

8. 考前 50 分鐘與 A4 對照（Exam Strategy & A4）

• 3 分鐘掃題：標出「定義題／計算題／證明題」。
• 35 分鐘作答：先定義與例子，再計算，最後證明。
• 10 分鐘檢查：gcd、模數、非空、順序、自逆、學號姓名。

A4 對照：

• 正面 01–05：對應本文 §1–§5 的定義與公式。
• 反面 06–09：對應本文 §3.2、§3.3、§4、§6 的證明骨架與易錯。
• 如果 A4 某一行看不懂，回到本文對應小節；不要只背 A4 的符號。

9. English Terminology（中英對照）

考試題目是英文時，先把這些字認出來。A4 因空間限制只留中文與符号；完整英文對照看這裡。

來源：NotebookLM 對話、Fraleigh A First Course in Abstract Algebra Ch.1 §1–7、iLearning 講義。定理號以課本為準。