你的進度
0/ 26 節已標記完成
下一節: 1.1 歐幾里得、Bézout與質因數分解
完成記錄儲存在此瀏覽器中。
這門課在網上
MATH3080 筆記裏的內容
數字只算這門課 26 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 72 · 定義 34 · 反例 26 · 概念視角 19 · 思想史 1 · 證明透視 28
第 1 章 · 3 節
整除與分解
推導歐幾里得算法,求解整係數線性方程,並證明質因數分解的唯一性。
- 1.1
歐幾里得、Bézout與質因數分解
推導歐幾里得算法,求解整係數線性方程,並證明質因數分解的唯一性。
- 1.2
歐幾里得算法的除法次數與相鄰斐波那契數
嚴謹分析歐幾里得算法的除法次數、相鄰斐波那契數為何達到極值,以及除法次數與位元複雜度的區別。
- 1.3
階乘的質數賦值與二項式係數的整除性
計算階乘中的質因子,並用進位解釋二項式係數的整除性。
第 2 章 · 2 節
同餘
透過最大公因數條件求解同餘式,再把相容的局部剩餘拼合成整體的解。
- 2.1
線性同餘與中國剩餘定理
透過最大公因數條件求解同餘式,再把相容的局部剩餘拼合成整體的解。
- 2.2
威爾遜定理、逆元配對與階乘的剩餘
嚴謹探討威爾遜定理、有限單位群中的逆元配對、合數模數下的階乘剩餘,以及由半階乘構造負一的平方根。
第 3 章 · 2 節
冪與階
透過單位解釋冪的週期性,證明費馬定理與歐拉定理,並區分指數上界與精確的階。
- 3.1
Fermat、Euler與乘法階
透過單位解釋冪的週期性,證明費馬定理與歐拉定理,並區分指數上界與精確的階。
- 3.2
Carmichael 通用指數與 Korselt 判據
研究模 n 的單位共同滿足的最小指數,通過中國剩餘定理和質數冪計算它,並完整證明 Korselt 判據。
第 4 章 · 2 節
算術函數
由質數冪構造因數和函數,並利用莫比烏斯函數對因數和進行反演。
- 4.1
算術函數與Möbius反演
由質數冪構造因數和函數,並利用莫比烏斯函數對因數和進行反演。
- 4.2
完全數與歐幾里得–歐拉定理
利用因數和函數證明偶完全數的分類。
第 5 章 · 2 節
原根
證明質數模存在原根,再把冪同餘化為關於指數的線性同餘。
- 5.1
原根與冪同餘
證明質數模存在原根,再把冪同餘化為關於指數的線性同餘。
- 5.2
原根提升與循環單位群分類
在所有奇質數冪構造生成元,並完整證明哪些合數模數具有原根。
第 6 章 · 3 節
二次剩餘
以格點計數證明 Euler 判別準則、Gauss 符號引理、兩條補充律及二次互反律。
- 6.1
二次剩餘、Gauss 引理與互反律
以格點計數證明 Euler 判別準則、Gauss 符號引理、兩條補充律及二次互反律。
- 6.2
非單位目標的平方同餘
利用賦值分類奇質數冪模數下的平方根。
- 6.3
雅可比互反律與無需因數分解的求值
將互反律由質數推廣至奇合數分母,證明歐幾里得式求值算法及其位元開銷界,並說明所得符號與平方根證書之間的分別。
第 7 章 · 4 節
丟番圖方程
二次丟番圖方程與遞降法。
- 7.1
用遞降法研究一個 Pell 方程
分類 x²−2y²=1 的解,並導出 √2 的有理逼近。
- 7.2
兩個平方數之和
證明整數可表示為兩個平方數之和的質因數判別法,並構造表示。
- 7.3
正整數勾股數組的分類
完整分類正整數勾股數組:兩兩互質、模 4 的奇偶性、參數 m 和 n 的存在唯一性、原始數組的伸縮,以及單位圓的有理參數化。
- 7.4
Pell 方程與二次單位的結構
由漸近分數的有界範數證明 Pell 解存在,以最小正單位分類全部解,並證明精確連分數搜尋會終止。
第 8 章 · 3 節
質數檢驗
追蹤強概質數檢驗並證明錯誤上界。
- 8.1
米勒–拉賓強概質數檢驗
由 1 的平方根構建強概質數檢驗,追蹤其判定過程,並解釋用盡檢查階段的一輪。
- 8.2
Miller–Rabin 計算追蹤與複雜度
追蹤強檢驗輪次並區分算術運算與位元運算成本。
- 8.3
米勒–拉賓錯誤的子群上界
證明奇合數的強說謊者至多佔一半的上界,並推導獨立重複的效果。
第 9 章 · 2 節
質數及其分佈
質數及其分佈
- 9.1
埃拉托色尼篩法與經過證明的質數表
嚴格講解埃拉托色尼篩法:定義、帶邊界檢查的有限算法、迴圈不變量證明、初等複雜度界,以及列舉質數與測試單個整數的區別。
- 9.2
切比雪夫界與質數倒數發散
利用中心二項式係數中的質數冪證明質數計數函數的 x/log x 量級,再在不使用質數定理的情況下證明質數倒數之和發散。
第 10 章 · 1 節
亨澤爾提升
亨澤爾提升
- 10.1
Hensel 提升、奇異分支與 p 進根
證明任意整係數多項式的精確逐位提升規則,構造相容 p 進根,並區分單根唯一性與奇異分支。
第 11 章 · 2 節
連分數
連分數
- 11.1
連分數、漸近分數與最佳逼近
推導漸近分數遞推及精確誤差式,證明第二類最佳逼近與 Legendre 判準。
- 11.2
二次無理數與最終週期性
透過完全商、有界的整數根式狀態以及可逆的簡約狀態映射,證明週期連分數定理的兩個方向。