数论基础

第一章：什么是数论？

第000007页

乍一看，“数论”这个词似乎神秘而宽泛。难道数学不都是关于数字的吗？这仅仅是数学的另一个名称吗？更谨慎的读者可能会注意到，几何和逻辑（例如）并不是真正关于数字的，即使有时会用到数字。但是，即使不包括这些主题，“数字的研究”听起来仍然过于宽泛。确实，“数论”一词是传统的，它专门指对整数的研究；也就是说，我们用来计数的数字

1, 2, 3, 4, ...

以及大胆添加的0，以及在方便的时候，负整数。不考虑分数、实数和复数。虽然在日常语言中这些抽象概念被称为数字，但传统上它们是在分析课程中研究的。

虽然整数起源于计数，但数论也不是关于计数的。高级计数技术的学习是一个独立的数学领域，称为组合数学。因此，数论是对整数及其相互关系的纯粹研究，特别是关于加法和乘法，这两者都将始终将整数转换为整数。为了理解这意味着什么，请考虑以下关于整数的问题

• 两个奇数的和是偶数还是奇数？乘积呢？
• 如果我们将n除以3，余数为2。如果我们将同一个数n除以17，余数为9。n的可能值是什么？
• 2的幂是否可以以“...324”结尾？
• 什么时候正整数n可以写成两个整数平方和？
• 如果n > 1，数字$1+{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n}}$是否可以成为整数？
• 方程$12x-57y=39$是否有整数解x和y？如果将39替换为38呢？

到目前为止，如上所述，数论可能看起来是一个相当抽象的话题，需要花费数月（数年？）来学习。确实，由于其表面上的纯洁性和与工业或科学应用的巨大距离，数论曾经被称为“数学女王”。

第000008页

情况已不再如此。虽然仍然被认为是抽象数学优雅的典范，但数论现在为信息论和计算机科学提供了具体的应用，包括密码学、数据压缩、纠错码和伪随机数生成，仅举几例。

尽管如此，学习数论最令人信服的理由在于它将简洁性和令人费解的复杂性独特地结合在一起，这为数学的美、惊喜和突然的清晰度提供了背景，这些对于那些喜欢数学的人来说是如此令人兴奋。

第二章：整数和算术

第000009页

我们的主要研究对象是整数集Z；也就是说，正整数和负整数

Z = {..., −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, ...}

用N表示自然数集也很方便；也就是说，正整数

N = {1, 2, 3, 4, 5, 6, 7, 8, ...}

我们假设读者熟悉整数的性质，这些性质应该在小学时就学过。特别是，整数是有序的，并且在加法、减法和乘法下是封闭的。此外，我们还假设N在加法和乘法下是封闭的。

以下恒等式总结了整数的代数性质。

定理2.1（整数算术的基本性质）

设$a,b,c\in Z$。

• $a+b=b+a$（加法是可交换的。）
• $a+(b+c)=(a+b)+c$（加法是结合的。）
• $a+0=a$（零是加法单位元。）
• $a+(-a)=0$（每个整数都有一个加法逆元。）
• $ab=ba$（乘法是可交换的。）
• $a(bc)=(ab)c$（乘法是结合的。）

• $a*1=a$（1 是乘法单位元。）
• $a(b+c)=ab+ac$（分配律）
• 如果 $ab=0$，则 a = 0 或 b = 0（或两者都为 0）。（整环）

上面列表中的最后一个性质暗示了以下的消去律。

命题 2.2 设 $a,b,c\in Z$，并假设 a ≠ 0。如果 $ab=ac$，则 $b=c$。

证明。由于 $ab=ac$，我们有 $ab-ac=0$。由于 a ≠ 0，定理 2.1 中的最后一个性质意味着 $b-c=0$，因此 $b=c$。

注意我们在上面的证明中没有说些什么。我们没有讨论“两边同时除以 a”。相反，证明使用了加法、减法

第 000010 页

和乘法的性质，而没有直接引用除法。这样拐弯抹角的原因将在理论展开的过程中变得清晰。