01 自然數／整數

• Peano：1∈N；S(n)∈N；S(n)≠1；S(m)=S(n)⇒m=n；歸納公理。
• Z 建構：(a,b)~(c,d)⇔a+d=b+c；[(a,b)] 代表 a−b；Z=(N×N)/~。
• 嵌入：N={1,2,…}⇒n↦[(n+1,1)]；N={0,1,…}⇒n↦[(n,1)]（以講義為準）。
• 等價關係：∀a a~a；a~b⇒b~a；a~b,b~c⇒a~c。
• Well-defined：換代表元結果不變。Z 加法：設 (a,b)~(a',b')、(c,d)~(c',d')，相加整理得 (a+c,b+d)~(a'+c',b'+d')。
• WOP：N 的每個非空子集有最小元；⇔ 歸納法。
• 除法：a=bq+r，b>0，0≤r<b；q,r 唯一。
• gcd：d=gcd(a,b)；∃x,y∈Z，ax+by=d（Bézout）；任何公因數都整除 d。
• Euclid：gcd(a,b)=gcd(b,a mod b)。
• Euclid's Lemma：p|ab⇒p|a 或 p|b。FTA：n>1 唯一質因數分解。

02 同餘／Z_n

• 同餘：a≡b (mod n)⇔n|(a−b)。
• 剩餘類：[a]={a+kn|k∈Z}；Z_n={[0],…,[n−1]}。
• Z_n well-def：a≡a′、b≡b′⇒a+b≡a′+b′、ab≡a′b′。
• 消去律：gcd(c,n)=1 且 ac≡bc⇒a≡b；一般 d=gcd(c,n)⇒a≡b (mod n/d)。
• 證：n|c(a−b)，gcd(c,n)=1⇒n|(a−b)。
• unit／zero divisor：unit⇔gcd(a,n)=1；zero divisor⇔a≠0 且 ∃b≠0,ab=0。
• 線性同餘：ax≡b (mod n)，d=gcd(a,n)。有解⇔d|b；有解時 d 個解：x=x₀+k(n/d)，k=0,…,d−1。
• Fermat：p 質數、p∤a⇒a^p−1≡1；等價 a^p≡a。
• Euler：gcd(a,n)=1⇒a^φ(n)≡1。
• Wilson：n>1，n 質數⇔(n−1)!≡−1 (mod n)。
• CRT：m_i 兩兩互質⇒模 ∏m_i 唯一解；不互質：gcd(m₁,m₂)|(a₁−a₂) 才有解。
• φ(n)：n∏_p|n(1−1/p)。

03 群／子群

• 二元運算：*:G×G→G；封閉。
• 群：∀a,b,ab∈G；∀a,b,c,(ab)c=a(bc)；∃e∀x,ex=xe=x；∀a∃a⁻¹,aa⁻¹=a⁻¹a=e。
• Abelian：ab=ba。
• 同構：雙射 φ:G→G′，φ(ab)=φ(a)φ(b)。
• 子群 H≤G：非空，且在 G 的運算下自身為群。
• 三條：封閉、e∈H、a∈H⇒a⁻¹∈H。
• 一步法：H≠∅，∀a,b∈H，ab⁻¹∈H。
• 有限子群法：H 有限非空且封閉。
• 證：a,a²,… 有限⇒a^m−n=e；a⁻¹=a^m−n−1。

04 循環群

• 定義：G=<a>={a^k|k∈Z}。
• 兩種 order：|G| 是元素個數；|a|=min{n∈Z_>0:aⁿ=e}，若無則無限；|a|=|<a>|。
• 公式：|a^s|=n/gcd(n,s)（前提 |a|=n）。
• 生成元：a^s 生成 G⇔gcd(s,n)=1；生成元 φ(n) 個。
• 子群：每個 d|n，恰一個 d 階子群=<a^n/d>。
• 證：取最小 m；除法 n=mq+r，r=0。
• 性質：循環群子群仍循環；循環⇒Abelian，反之不然（V）。
• 分類：無限循環≅Z；n 階循環≅Z_n。

05 生成集／Cayley

• 生成集：<S>=含 S 的最小子群=S 與逆元的有限乘積。
• Cayley：頂點=群元素；弧 x→xg（右乘）；g=g⁻¹ 畫無向邊。
• 性質：連通；每點每 g 一進一出；唯一邊 xg；同字詞平移一致。
• 例：Z₈ S={1} 8-cycle；V S={a,b} 4-cycle；D₄ S={r,s}：r-出弧、s-邊。

06 證明骨架

• e 唯一：e=e e′=e′。
• a⁻¹ 唯一：b=b e=b(ac)=(ba)c=ec=c。
• 倒置律：驗 (ab)(b⁻¹a⁻¹)=e，再用逆元唯一。
• 消去律：ab=ac⇒左乘 a⁻¹⇒b=c。
• xa=x⇒a=e：左乘 x⁻¹。
• abc=e⇒c⁻¹=ab：右乘 c⁻¹。
• ax=b⇒x=a⁻¹b；ya=b⇒y=ba⁻¹。
• 一步子群：取 x⇒e；e,x⇒x⁻¹；x,y⁻¹⇒xy；結合繼承。
• Z_n well-def：a≡a′、b≡b′ (mod n)⇒(a+b)−(a′+b′)=(a−a′)+(b−b′)≡0。
• Wilson：1,p−1 自逆；其餘兩兩配對逆元⇒(p−1)!≡−1。

07 易錯 13 條

• 消去前看 gcd(c,n)；不是隨時能消。
• φ(n) 是保證週期，不是最小階；最小階 | φ(n)。
• |a^s| 的 n 是 |a|，不是 |G|。
• 非交換群不能換順序；(ab)⁻¹=b⁻¹a⁻¹。
• abc=e⇒c⁻¹=ab，不是 ba。
• xa=x 在群裡可推 a=e（x 有逆元）。
• abc=acb⇒bc=cb，只證明 b,c 可交換，不是全群。
• 子群先寫 H≠∅；有限法只用有限子集；Z⁺ 反例。
• Cayley 是右乘；自逆元素不畫箭頭。
• unit⇔gcd(a,n)=1；zero divisor 通常 gcd>1（0 除外）。
• CRT 先檢查兩兩互質。
• Fermat 要 p∤a；Euler 要 gcd(a,n)=1。
• Wilson 是 iff，不是只有 ⇒。

08 經典群

• Z_n：n 階，Abelian。
• Z_n^×：φ(n) 階，Abelian。
• S_n：n! 階；n≥3 非 Abelian。
• D_n：2n 階；n≥3 非 Abelian。
• V：4 階，Abelian 非循環。
• GL(n,R)：無限；n≥2 非 Abelian。

09 計算模板

• 7⁻¹ mod 31：31=4·7+3；7=2·3+1⇒1=9·7−2·31⇒9。
• 6x≡9 mod 15：d=3；2x≡3 mod 5⇒x≡4,9,14。
• 3¹⁰³ mod 100：φ(100)=40；103=2·40+23；3²³≡27。
• Z₁₂：|4|=12/4=3；生成元 1,5,7,11；子群 d|12。

10 精確用語

• 任取=arbitrary；存在=exists；唯一=unique；恰有一個=exactly one。
• 若且唯若=iff，兩方向都要證；反之=converse。
• 非空=H≠∅；子集≠子群。
• 寫左乘／右乘，不要寫「同除」；結合律說繼承。
• 代表元；well-defined=與代表元選擇無關。
• 引用公理寫 G1–G4；假設與結論分開寫。

11 定理假設

• Division：b>0；Fermat：p∤a；Euler：gcd(a,n)=1；Wilson：n>1；CRT：兩兩互質。
• 一步法：H≠∅；有限法：H 有限；|a^s|：|a|=n。
• gcd：S={ax+by>0} 取最小 d；除法 a=dq+r，r∈S∪{0}⇒r=0；c|a,b⇒c|d；d1|d2,d2|d1⇒d1=d2。
• Division：S={a−bk≥0} 取最小 r；r≥b⇒r−b∈S 更小；b(q−q')=r'−r、|r'−r|<b⇒0。
• FTA：強歸納存在；唯一用 Euclid：p1|q1…⇒p1=qj，對稱 p1=q1，消去後歸納。

12 證明開頭／結尾

• 要證 H≤G：先 H≠∅；任取 a,b∈H；證 ab⁻¹∈H；結合律繼承。
• 要證 well-defined：設代表元…；證結果不變。
• 要證唯一：設有兩個…；證相等。
• 要證 ax=b：左乘 a⁻¹；ya=b：右乘 a⁻¹。