你的进度
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
Miller–Rabin 误差的一个子群界
证明奇合数的强说谎者至多占一半,并推导独立重复检验对误差的影响。
第 9 章 · 2 节
素数及其分布
素数及其分布
- 9.1
埃拉托色尼筛法与经过证明的素数表
严格讲解埃拉托色尼筛法:定义、带边界检查的有限算法、循环不变量证明、初等复杂度界,以及列举素数与测试单个整数的区别。
- 9.2
切比雪夫界与素数倒数发散
利用中心二项式系数中的素数幂证明素数计数函数的 x/log x 量级,再在不使用素数定理的情况下证明素数倒数之和发散。
第 10 章 · 1 节
亨泽尔提升
亨泽尔提升
- 10.1
Hensel 提升、奇异分支与 p 进根
证明任意整系数多项式的精确逐位提升规则,构造相容 p 进根,并区分单根唯一性与奇异分支。
第 11 章 · 2 节
连分数
连分数
- 11.1
连分数、渐近分数与最佳逼近
推导渐近分数递推及精确误差式,证明第二类最佳逼近与 Legendre 判准。
- 11.2
二次无理数与最终周期性
通过完全商、有界的整数根式状态以及可逆的简约状态映射,证明周期连分数定理的两个方向。