Skip to main content

《初等数论》

参考资料​

引入​

初等数论（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\Rightarrow a^{p-1}\equiv 1\pmod p
欧拉定理gcd⁡(a,m)=1⇒aφ(m)≡1(modm)\gcd(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1\pmod m
威尔逊定理pp 素数   ⟺  (p−1)!≡−1(modp)\iff (p-1)!\equiv -1\pmod p
中国剩余定理模两两互素时同余方程组可解

学习建议​

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