跳到正文

MATH3080

数论

整除、同余、算术函数、原根、二次剩余、丢番图方程、素性检验与连分数,附证明、例题及习题解答。

11 章 · 26 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 26 节已标记完成

下一节: 1.1 欧几里得、Bézout与素因数分解

完成记录保存在此浏览器中。

这门课在网上

MATH3080 笔记里的内容

定理卡
72
定义
34
反例
26
概念视角
19
思想史
1
证明透视
28

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 26 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 72 · 定义 34 · 反例 26 · 概念视角 19 · 思想史 1 · 证明透视 28

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 26 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 3 节

整除与分解

推导欧几里得算法,求解整系数线性方程,并证明素因数分解的唯一性。

定理 11 · 定义 5反例 3视角 3思想史 1证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    欧几里得、Bézout与素因数分解

    推导欧几里得算法,求解整系数线性方程,并证明素因数分解的唯一性。

  2. 1.2

    欧几里得算法的除法次数与相邻斐波那契数

    严谨分析欧几里得算法的除法次数、相邻斐波那契数为何达到极值,以及除法次数与位复杂度的区别。

  3. 1.3

    阶乘的素数赋值与二项式系数的整除性

    计算阶乘中的素因子,并用进位解释二项式系数的整除性。

第 2 章 · 2 节

同余

通过最大公约数条件求解同余式,再把相容的局部剩余拼装成整体解。

定理 9 · 定义 3反例 3视角 1证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    线性同余与中国剩余定理

    通过最大公约数条件求解同余式,再把相容的局部剩余拼装成整体解。

  2. 2.2

    威尔逊定理、逆元配对与阶乘的剩余类

    以有限单位群中的逆元配对,证明威尔逊定理,讨论合数模数下的阶乘及半阶乘给出的负一平方根。

第 3 章 · 2 节

幂与阶

通过单位解释幂的周期性,证明费马定理与欧拉定理,并区分指数上界与精确的阶。

定理 7 · 定义 3反例 3视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    Fermat、Euler与乘法阶

    通过单位解释幂的周期性,证明费马定理与欧拉定理,并区分指数上界与精确的阶。

  2. 3.2

    Carmichael 通用指数与 Korselt 判据

    研究模 n 的单位共同满足的最小指数,通过中国剩余定理和素数幂计算它,并完整证明 Korselt 判据。

第 4 章 · 2 节

算术函数

由素数幂构造因数和函数,并利用莫比乌斯函数对因数和进行反演。

定理 4 · 定义 3反例 1视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    算术函数与Möbius反演

    由素数幂构造因数和函数,并利用莫比乌斯函数对因数和进行反演。

  2. 4.2

    完全数与欧几里得–欧拉定理

    利用因子和函数证明偶完全数的分类。

第 5 章 · 2 节

原根

证明素数模存在原根,再把幂同余化为关于指数的线性同余。

定理 4 · 定义 2反例 2视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    原根与幂同余

    证明素数模存在原根,再把幂同余化为关于指数的线性同余。

  2. 5.2

    原根提升与循环单位群分类

    在所有奇素数幂构造生成元,并完整证明哪些合数模数具有原根。

第 6 章 · 3 节

二次剩余

以格点计数证明 Euler 判别准则、Gauss 符号引理、两条补充律及二次互反律。

定理 6 · 定义 3反例 3视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    二次剩余、Gauss 引理与互反律

    以格点计数证明 Euler 判别准则、Gauss 符号引理、两条补充律及二次互反律。

  2. 6.2

    非单位目标的平方同余

    利用赋值分类奇素数幂模数下的平方根。

  3. 6.3

    雅可比互反律与无需因数分解的求值

    将互反律从素数推广到奇合数分母,证明欧几里得式求值算法及其比特开销界,并说明所得符号与平方根证书之间的区别。

第 7 章 · 4 节

丢番图方程

二次丢番图方程与递降法。

定理 11 · 定义 4反例 4视角 3证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    用递降法研究一个 Pell 方程

    分类 x²−2y²=1 的解,并导出 √2 的有理逼近。

  2. 7.2

    两个平方数之和

    证明整数可表示为两个平方数之和的素因数判别法,并构造表示。

  3. 7.3

    正整数勾股数组的分类

    完整分类正整数勾股数组:两两互素、模 4 的奇偶性、参数 m 和 n 的存在唯一性、原始数组的伸缩,以及单位圆的有理参数化。

  4. 7.4

    Pell 方程与二次单位的结构

    由渐近分数的有界范数证明 Pell 解存在,以最小正单位分类全部解,并证明精确连分数搜索会终止。

第 8 章 · 3 节

素性检验

追踪强概率素数检验并证明误差界。

定理 8 · 定义 3反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    米勒–拉宾强概率素数检验

    从 1 的平方根出发构建强概率素数检验,追踪其判定过程,并解释用尽检查阶段的一轮。

  2. 8.2

    Miller–Rabin 计算追踪与复杂度

    追踪强检验轮次并区分算术运算与比特运算代价。

  3. 8.3

    Miller–Rabin 误差的一个子群界

    证明奇合数的强说谎者至多占一半,并推导独立重复检验对误差的影响。

第 9 章 · 2 节

素数及其分布

素数及其分布

定理 6 · 定义 3反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    埃拉托色尼筛法与经过证明的素数表

    严格讲解埃拉托色尼筛法:定义、带边界检查的有限算法、循环不变量证明、初等复杂度界,以及列举素数与测试单个整数的区别。

  2. 9.2

    切比雪夫界与素数倒数发散

    利用中心二项式系数中的素数幂证明素数计数函数的 x/log x 量级,再在不使用素数定理的情况下证明素数倒数之和发散。

第 10 章 · 1 节

亨泽尔提升

亨泽尔提升

定理 2 · 定义 2反例 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    Hensel 提升、奇异分支与 p 进根

    证明任意整系数多项式的精确逐位提升规则,构造相容 p 进根,并区分单根唯一性与奇异分支。

第 11 章 · 2 节

连分数

连分数

定理 4 · 定义 3反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    连分数、渐近分数与最佳逼近

    推导渐近分数递推及精确误差式,证明第二类最佳逼近与 Legendre 判准。

  2. 11.2

    二次无理数与最终周期性

    通过完全商、有界的整数根式状态以及可逆的简约状态映射,证明周期连分数定理的两个方向。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情