1
一般情况下，0不参与数论问题的讨论，所以在以后的讨论中，把正整数和自然数看成等价的概念。
2
第一章 整除
3
定理 1.1.2. 设m ∈ N ， m ̸= e，那么，必有唯一的n ∈ N 使得n+ = m， 即N 中每个不等于e的元素必是某个元素的后继，e是唯一一个没有后继的 元素。 定理 1.1.3 (归纳证明原理). 设P (n)是关于自然数n的一种性质或者命题。 如果当n = e时， P (e)成立，以及有P (n)成立必可推出P (n+ )成立，那么， P (n)对所有的n ∈ N 都成立。 归纳证明原理作为一种相当基础的证明算法，在解决一些关于集合的 命题的时候往往会被使用。在验证某些恒等式的时候，由于等式的变量取 值为正整数，也可以巧妙地使用归纳证明原理来证明。
第四章 不定方程 4.1 4.2 4.3 一次不定方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . Pythagoras 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . Lagrange 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . .
初等数论1
张文泰2 20100102-rev20
1
本文介绍了非常多的基础理论的知识，是为了形成一个完整的初等数论体系，有助
于一个良好的数学基础的形成。 2 e-mail: rchardx@
目录
第一章 整除 1.1 1.2 1.3 1.4 1.5 1.6 Peano 公理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 整除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 带余除法与辗转相除法 . . . . . . . . . . . . . . . . . . . . . . 最大公约数和最小公倍数 . . . . . . . . . . . . . . . . . . . . . 算术基本定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . 阶乘的分解式 . . . . . . . . . . . . . . . . . . . . . . . . . . .
第三章 同余方程 3.1 3.2 3.3 3.4 3.5 同余方程基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . 一次同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . 一次同余方程组，孙子定理 . . . . . . . . . . . . . . . . . . . 模为素数的二次同余方程 . . . . . . . . . . . . . . . . . . . . . Legendre 符号，Gauss 二次互反律 . . . . . . . . . . . . . . .
1
第一章
整除
整除理论是数论的基础，它主要是对整数除法运算的内容作抽象的、 系统的总结。本章的主要内容是算术基本定理，同时有对其他基础理论的 讨论。
1.1 Peano 公理
本节将会介绍自然数1 最重要的两个性质，自然数的归纳原理和最小自 然数原理。 自然数的本质属性是由归纳属性刻画的，它是自然数公理化定义的核 心。自然数集合严格的抽象的定义是由 Peano 公理给出的，它刻画了自然 数的本质属性，并导出有关的运算和性质。
顺序
对给定的a, b ∈ N ，如果存在x ∈ N ，使得b = a + x，那么，我们就
说b在a之后（或a在b之前） ，也说b大于a（或者a小于b） ，记作 b>a 由此推出 定理 1.1.4. 对任意的a, b ∈ N ，a = b, a > b, a < b有且仅有一个成立。 or a<b
定理 1.1.5 (最小自然数原理). 自然数集合N 的任一子集T 中都存在一个最小 的元素。 定理 1.1.6 (最大自然数原理). 对于自然数集合N 的一个子集M ，如果M 存 在上界，那么M 中必定存在一个最大的元素。 最小自然数原理是常用的第二种数学归纳法的基础。 定理 1.1.7 (第二种数学归纳法). 设P (n)是关于自然数n的一种性质或者命 题。如果 (i) 当n = 1时，P (1)成立； (ii) 设n > 1，若对所有的自然数m < n，P (m)成立，则必有P (n)成立。 那么，P (n)对所有自然数n成立。 这一章完全是各种基础的概念，作为一个背景简单说明一下。下面开 始介绍比较重要而又很基础的一些内容。
1.3 带余除法与辗转相除法
带余除法作为数论中最常使用的基本方法，具有很高的实用性。它是 数论证明中最重要、最基本、最直接的工具。 IMO 中的大部分数论题目
第一章 整除
6
都可以用带余除法解决，虽然过程可能不太直观，但是并不能影响它的地 位。 定理 1.3.1 (带余数除法). 设a，b是两个给定的整数，a ̸= 0。那么一定存在 唯一的一对整数q 与r，满足 b = qa + r, 此外，a|b的充要条件是r = 0。 在具体应用的时候，往往并不要求r满足最小性，第二种形式如下： 定理 1.3.2. 设a，b是两个给定的整数，a ̸= 0，再设d是一给定的整数。那么 一定存在唯一的一对整数q1 与r1 ，满足 b = q1 a + r1 , 此外，a|b的充要条件是a|r1 。 上面的定理可以由定理1.3.1推出。我们一般把式1.1中的r称为b被a除后 的最小非负余数。式1.2中的r1 称为绝对最小余数。 下面是一个关于整数分类的推论： 推 论 1.3.3. 设a > 0。 任 一 整 数 被a除 后 所 得 的 最 小 非 负 余 数 是 且 仅 是0, 1, . . . , a − 1这a个数中的一个。 例题 1.3.1. 设a > 2是奇数。证明： (i) 一定存在正整数d ≤ a − 1，使得a|2d − 1。 (ii) 设d0 是满足 (i) 的最小正整数d。那么， a|2h − 1(h ∈ N )的充要条件 是d0 |h。 证. 先证 (i)。考虑以下a个数： 20 , 21 , 22 , . . . , 2a−1 显然，a 2j (0 ≤ j < a)。由定理1.3.1知，对于每一个j ，0 ≤ j < a， 2j = qj a + rj , 0 < rj < a d ≤ r < |a| + d (1.2) 0 ≤ r < |a| (1.1)
(ii) a|b且b|c ⇒ a|c； (iii) a|b且a|c ⇐⇒ 对任意的x, y ∈ Z 有a|bx + cy 。该定理还有其一般形式； (iv) 设m ̸= 0。那么，a|b ⇐⇒ ma|mb； (v) a|b且b|a ⇒ b = ±a； (vi) 设b ̸= 0。那么，a|b ⇒ |a| ≤ |b|。 例题 1.2.1. 设a, b是两个给定的非零整数，且有整数x, y ，使得ax + by = 1。 证明：若a|n且b|n，则ab|n。 证. 由n = n(ax + by ) = (na)x + (nb)y ，及ab|na，ab|nb即得所要的结论2 。 2 定义 1.2.2. 设整数p ̸= 0, ±1。如果它除了显然约数±1, ±p外没有其他的约 束，那么p被称为是 不可约数，也叫做 素数3 。若a ̸= 0, ±1且a不是不可约 数，则a称为合数。 下面几个定理是容易得到的 定理 1.2.2. 若a是合数，则必有一个素数p满足p|a。 定理 1.2.3. 若整数a ≥ 2，则a必可以表示为若干个素数的乘积，即 a = p1 p2 p3 · · · ps 由定理1.2.3可以得到下面的推论 推论 1.2.4. 设整数a ≥ 2。
2 3
事实上，满足题中的所给条件的a, b是互素的。 以后我们提到素数的时候，若无特殊情况，都假定它是正的。
第一章 整除 1. 若a是合数，则必有素数p，p ≤ a1/2 ； 2. 若a有定理1.2.3中的表达式，则必有不可约数p，p ≤ a1/s 。
5
推论1.2.4给出了一种在某一范围内寻找素数的有效方法。我们一般称 之为 Eratosthenes 筛法。由于比较容易推出，所以不再赘述。 定理 1.2.5. 素数有无穷多个。 证. 假设只有有限个素数，令它们为p1 , p2 , . . . , pk 。考虑Ek = p1 p2 · · · pk +1， 可 以 发 现， Ek > 2且 必 有 某 个pi |Ek ，所 以pi |Ek − p1 p2 · · · pk ，而 Ek − p1 p2 · · · pk = 1，但pi ≥ 2，显然不可能，矛盾，所以假设错误。 上面提到了Ek ，我们称之为欧拉数。下面是前几项的结果： E1 = 3, E2 = 7, E3 = 31, E4 = 211, E5 = 2311, E6 = 30031, E7 = 510511, . . . 对于欧拉数，还没有关于其中是否存在无限多素数或合数的结论。一 个关于它们的显然性质是对于正整数m ̸= n， (Em , En ) = 1。另外，对 于En (n > 1)，我们可以写出表达式
Peano 公理 设N 是一个非空集合，满足以下条件： (i) 对每一个元素n ∈ N ，一定有唯一的一个N 中的元素与之对应，这个 元素记作n+ ，称为n的后继元素。 (ii) 有元素e ∈ N ，它不是任一元素的后继。 (iii) N 中的元素至多是一个元素的后继。 (iv) （归纳公（原）理）设S 是N 的一个子集合，e ∈ S 。如果n ∈ S ，则必 有n+ ∈ S ，那么，S = N 。 由此立刻可以得出几个定理： 定理 1.1.1. 对任意的n ∈ N 有n ̸= n+ 。