Skip to main content

《初等数论》

Summary

关于整数性质的数学分支导览。以「整除 → 同余 → 数论函数 → 不定方程」为主线，串起素数与唯一分解、按余数归类的同余、定义在整数上的函数，最后回到求整数解的方程。四章分别对应整除与素数、同余、积性函数、不定方程，并附速查表列出算术基本定理、裴蜀、费马小、欧拉、威尔逊、中国剩余定理。学习建议强调手算、把每个定理对应到具体算法，以及与离散数学的联动。现代密码学多建立在这套体系之上。

参考资料​

引入​

初等数论（Elementary Number Theory）是关于 整数性质 的数学：整除、素数、同余、不定方程。

它不依赖高等分析工具，只用整数的加减乘和「能否整除」这点最朴素的结构，问题却往往极其精妙。许多一句话就能说清的问题（如孪生素数、哥德巴赫猜想）至今无人能解。

整门课的逻辑链条很清晰：

整除→同余→数论函数→不定方程\text{整除}\to\text{同余}\to\text{数论函数}\to\text{不定方程}

从「能否整除」出发，引出素数与唯一分解；把整数按余数归类得到同余；进一步研究定义在整数上的函数；最后回到具体方程求整数解。现代密码学（RSA、椭圆曲线、零知识证明）几乎全建立在这套体系之上。

章节大纲​

  • 整除与素数：整除性质与证明、带余除法、欧几里得算法、扩欧回代、裴蜀定理、gcd⁡/lcm⁡\gcd / \operatorname{lcm}、算术基本定理、试除与筛法。
  • 同余：同余性质、剩余系、欧拉函数、快速幂与降幂、费马小定理与欧拉定理、模逆元、一次同余方程、中国剩余定理、原根与二次剩余。
  • 积性函数：积性函数、欧拉函数、因子函数、莫比乌斯函数、狄利克雷卷积、莫比乌斯反演、线性筛、完全数。
  • 不定方程：一次不定方程、勾股数、佩尔方程、无穷递降法、费马大定理、平方和定理、取模筛除与韦达跳跃。

速查表​

关键定理一览​

定理内容
算术基本定理每个 n>1n>1 唯一分解为素数乘积
裴蜀定理ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 有整数解
费马小定理gcd⁡(a,p)=1  ⟹  ap−1≡1(modp)\gcd(a,p)=1\implies a^{p-1}\equiv 1\pmod p
欧拉定理gcd⁡(a,m)=1  ⟹  aφ(m)≡1(modm)\gcd(a,m)=1\implies a^{\varphi(m)}\equiv 1\pmod m
威尔逊定理pp 素数   ⟺  (p−1)!≡−1(modp)\iff(p-1)!\equiv-1\pmod p
中国剩余定理模两两互素时同余方程组可解

学习建议​

  • 手算最重要。 初等数论的题目大多依赖灵活的代数变形与对模运算的熟练度。
  • 联系算法。 欧几里得算法、快速幂、扩欧、CRT、线性筛——每个定理都对应一个具体可实现的算法。
  • 与 离散数学 联动。 同余是 等价关系 的典型例子；Zp\mathbb{Z}_p 是 代数结构 中域的典型例子。