Skip to main content

《初等数论》

参考资料​

引入​

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

它不依赖高等分析工具，但问题往往极其精妙。许多看似简单的问题（如孪生素数、哥德巴赫猜想）至今未解。

现代密码学（RSA、椭圆曲线、零知识证明）几乎全建立在初等数论之上。

章节大纲​

  • 整除与素数：整除性质、带余除法、gcd⁡/lcm⁡\gcd / \operatorname{lcm}、唯一分解定理。
  • 同余：同余性质、欧拉函数、费马小定理、CRT、线性同余方程。
  • 积性函数：欧拉函数、莫比乌斯函数、狄利克雷卷积、莫比乌斯反演。
  • 不定方程：裴蜀定理、勾股数、佩尔方程、费马大定理简介。

速查表​

关键定理一览​

定理内容
算术基本定理每个 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 是 代数结构 中域的典型例子。