《数论导论》——第一章及第五章节选外文翻译资料

An Introduction to the Theory of Numbers

——第一章及第五章节选

G.H.Hardy E.M.Wright

1. 素数（1）

1.1 整除性

数

称为有理数，或简称为整数。数

称为非负整数。数

称为正整数。正整数构成算数的主要对象，但它基本上常被视为整数或者某个更大范围内的数的一个子集。

以后我们用字母

表示整数，它们有时（但并不总是如此）会服从某些进一步的限制条件，比如正数或非负数这样的显示。我们也常用“数”来指代“整数”（或表示“正整数”等），在正文中的含义明确无误时，我们考虑的就仅仅是这种特殊类型的数。

称一个整数能被另一个整数整除，假设存在第三个整数使得

如果和都是正数，则必定为正数。用记号

来表示被整除，或是的一个因子。于是有

且对每个不为零的数均有。有时也用

来表示与相反的含义。显然有

（假设），

以及

（对于任何整数和）。

1.2素数

在1.2节到1.9节中，我们考虑的数一般都是正整数。^① 正整数中有一个特别重要的子集，即素数合集。数称为素数，如果

(i)

(ii)没有除了1和意外的正因子。

例如，37是一个素数，要特别注意的是1不算作素数，这一点很重要。在第一章以及第二章例，我们始终用字母表示素数。^②

大于1且不是素数的数称为合数。

下面，我们引入第一个定理：

定理1 除了1以外的每个正整数都是素数的乘积。

要么是素数（此时不需要证明了），要么有大于1且小于的因子。设 这些因子中最小的一个，那么必定为素数，否则

则

这与的定义矛盾。

因此，要么是素数，要么可以被一个小于的素数（比方说）整除。在后一种情形中，有

这里的要么是素数，（此种情形的证明已经完成），要么可以被一个小于的素数整除，此时有

重复这个方法，得到一列递减的数，它们全部都大于1，对其中每个数，都同样有以上两种可能性成立。但迟早我们必定会接受第一种可能性，此时得到的已经是一个素数，比如记之为，这样就得到

(1.2.1)

例如

如果，那么和不可能都大于。于是任何合数必定可以被一个不超过的素数整除。

(1.2.1)式中的素数不一定是互不相同的，也不一定非要按照某个特定的次序排列。如果把他们按照递增的顺序排列，把相同的素数合写成单一的因子，并适当改变记号，就得到

(1.2.2)

称被表示成了标准型。

1. 同余和剩余

5.1．最大公约数和最小公倍数。

我们已经对和的最大公约数进行了定义。关于最大公约数，有这么一个简单的公式。

我们用表示和之中较小的数，用表示和之中较大的数。例如，

定理50. 如果

^① ，并且

那么

这个定理是对定理2和最大公约数的定义的一个总结。

两个整数和的最小公倍数是可以被这两个数整除的最小的正整数。我们用来表示，所以

而且是具有这个性质的最小的数。

定理51. 在定理50中，有

^①

从定理50和定理51我们推断

定理52

如果，和就互素。例如中，任意两个数互为素数，那么这几个数是互素的。

也就是说表示除了1没有其他数能同时被这几个数整除。

有时我们会说，“和没有共同的因数”，其实这句话的意思是除了1，他们没有其他共同的因数，即他们是互素。

5.2 . 同余和类，余数

如果，能整除那么就说和关于模同余，用公式可表示为

这个定义不引入任何新的想法，因为“”和“”具有相同的含义，但每个标记法都有它各自的优点。在2.9章节中，我们已经不同的情景下使用过“模数”，但是不同的含义不会造成任何混淆。^①

如果，那我们说和不同余。

如果，那我们就把称为模m的一耳光剩余。如果，那么就是模 的最小剩余。^②因此，两个数和同余的话，就是说对于同一个模，他们有相同的余数。模的一个剩余类是由与某个给定的剩余同余的所有数所组成的一个雷，这个类的每一个成员都叫做这个类的一个代表。显然，总共有个剩余类，它们分别由

这些数字作为代表。这个数组成的集合，或者任何个分别属于这个剩余类的数组成的一个集合，都成为模的一个完全剩余系，或简称为模的一个完系。

同余是日常生活中具有重大的现实意义。例如，“今天是星期六”就是从某个确定的日期开始所经过的天数关于模7的一个痛与性质，这个性质通常要比某个时间点（例如创始伊始）开说所经过的天数重要得多。课程表和列车时刻表同样也是同余表，课程表中设计的模是365，7，和24。

想知道找发生了某个特定事件的某一天究竟是星期几，实际上就是对模7解一个算数问题。在这样的算数中，同余的数是等价的，因此这种算数完全是有限的系统，其中所有的问题都可以通过尝试来获得解答。例如，一个讲座每两天举办一次（包括星期天）企鹅第一次讲座在星期一举行，那么第几次讲座首次在星期二举办呢？如果这次讲座是第次，那么有

通过尝试可以求得最小的正数解是

从而第五次讲座将会在星期二开奖，而且这也僵尸第一次在星期二举办的讲座。

类似的，可以用尝试法求得同余式

有4个解，即为

有时候，即使出现的变量不是整数，我们也使用同余符号，这样做有时是很方便的。比如说，只要是的整数倍，就可以写成

例如，这样就有

5.3 同余的基本性质

（i）

（ii）

（iii）

又如果就有

（iv）

（v）

如此类推，最后，如果为任意的正数系数多项式，就有

（vi）

定理53 如果并且那么。特别的是，如果那么

如果是能够整除的p的最高幂，那么或者，于是有。这对于的每个素因子而言都是城里的，所以这条定理很容易推广到多个同余式的情形。

5.4 线性同余

5.3节介绍的性质（i）至性质（vi）与普通的带式方程的性质很像，但是我们很快就会遇到它们之间的一个差别。下面的性质在同余式中就未必成立：

比如

但是

接下来我们要研究在这个方向上有什么结果是成立的。

定理54 如果，那么

反过来也成立。

因为则有

那么

又因为，所以

^①

这就这就证明了定理。特别地，有

定理55 如果，那么

反过来也成立。

定理56。 如果是模的一个完全剩余系，而且，那么也是模的一个完全剩余系。

根据定理55，由可以推导出，这只有当的时候才可能成立。更一般的来说，如果，那么

也是模的完全剩余系。

定理57 如果，那么

（5.4.1）

有解，当且仅当，且有解时它恰有个解。特别地是，如果，那么该同余式只有一个解。

定理57中的同余式等价于

因此，这个结果部分地包含在定理25之中。当我们说到同余式“恰有个”解的时候，自然理解成吧同余的解看成同样的解。

如果，定理57就是定理56的推论。如果，则同余式（5.4.1）显然是不可解的，除非有，如果，那么

故而该同余式等价于

（5.4.2）

由于所以（5.4.2）恰好有一个解。如果这个解释

那么

而（5.4.1）的完全解集就可以通过给取所有的值来求得，这里y的取值要使得关于模互补同余。

由于

从而恰好有个解，这些节可以表示成

这就证明了定理。

5.5 欧拉函数

用来记不大于m的正整数中与 互素的整数的个数，也就是说满足

^①

的整数的格式。如果与互素，那么任何一个与同余的数也与互素。于是有个与互素的剩余类，从每个这样的剩余类中任意取出一个数所得到的任何一组个剩余作成的集合都称为一个与互素的完全剩余系^②。一个这样的完全系是个小于且与互素的数组成的集合。

定理58 如果是一个与互素的完全剩余系，且，那么

仍然是一个与 互素的完全剩余系。

显然，第二组数也都是与互素，且如同定理56的证明中那样，它们没有任何将个数是同余的。

定理59 假设，且取遍模的一个完全剩余系，取遍模的一个完全剩余系，那么取遍模的一个完全剩余系。

这里有个数。如果

那么

所以

类似的有

从而着个数都是互不同余的。于是它们构成了模的一个完全剩余系。

一个函数成为是积性的，如果就蕴含

定理60 是积性的。

如果，那么根据定理59可知，当和分别取模和模的完全剩余

系时，取遍模的一个完全剩余系，又有

从而这个小于且与互素的数是这个数的最小剩余，其中与互素，而与互素，从而有

=

附带我们还证明了

定理61 如果，取遍一个与互素的完全剩余系，而则取遍一个与互素的完全剩余系，那么取遍模的一个完全剩余系。

现在可以对m的任意的值求出的值。根据定理60可见，只要对m为互素数幂的情形来计算就行了，小于的正数一共有-1个，其中有个事p的倍数，剩下的数都与p互素，从而有

故而的一般的值可由定理60得出。

外文文献出处：

剩余内容已隐藏，支付完成后下载完整资料

---

英语原文共 642 页，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[287207]，资料为PDF文档或Word文档，PDF文档可免费转换为Word