初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论（用代数结构的方法研究数论）。

古希腊

古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数（如亲和数、完全数、多边形数）及特殊不定方程的研究。公元前4世纪，欧几里得的《几何原本》通过102个命题，初步建立了整数的整除理论。他关于“素数有无穷多个”的证明，被认为是数学证明的典范。

初等数论已经有2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。公元前250年古希腊数学家埃拉托斯特尼发明了一种筛法。2000年来，数论学的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心血。后来发现埃拉托塞尼筛法可以转换成为一个素数产生的公式：

公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：

（一）“要得到不大于某个自然数n（不等于0）的所有素数，只要在2至n中将不大于的素数的倍数全部划去即可”。

（二）将上面的内容等价转换：“如果n是合数（非0自然数），则它有一个因子d满足

”。

（三）再从（二）得到等价的逆否命题：“若自然数n不能被不大于的任何素数整除，则n是一个素数”。

（四）上述的（三）可以用符号如此表达：

其中

顺序地表示素数2，3，5，...。对以上的数（即为N被相除所得之余数），有（余数不为0）。

即N不能是形。若是，则N是一个素数。

（五）可以把上述的式（1）用同余式组表示：

例如，29不能够被以下的任何素数,如2，3，5整除，。

，所以29是一个素数。

由于（2）的模

两两互素，根据孙子定理（中国剩余定理）知，（2）式在的意义上有唯一解。

例如时，解得。求得了（3，3）区间的全部素数。

例如：当时，，解得；，解得。如此，求得了（5，5 ）区间的全部素数。

仿此下去可以求得任意给常数以内的全部素数。

(六)用程序方法求素数。“若一个自然数n，判断是否整除，先判断其能否整除2，若不能再判断其能否整除3，依次向下判断，当时，判断结束。”如果所有判断都不能整除，则自然数N为素数。

公元3世纪，丢番图研究了若干不定方程，并分别设计巧妙解法，故后人称不定方程为丢番图方程。17世纪以来，皮耶·德·费玛、莱昂哈德·欧拉、高斯等人的工作大大丰富和发展了初等数论的内容。

古代中国

中原地区古代对初等数论的研究有着光辉的成就，《周髀算经》、《孙子算经》、《张丘建算经》、《数书九章》等文言文献上都有记载。中国剩余定理比欧洲早500年，西方常称此定理为中国剩余定理，秦九韶的大衍求一术也驰名世界。初等数论不仅是研究纯粹数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。

初等数论有以下几部分内容：

1.整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里得的辗转相除法、算术基本定理、素数个数无限证明。

2.同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、中国剩余定理（即中国剩余定理）等等。

3.连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。

4.不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。

5.数论函数。比如欧拉函数、莫比乌斯变换等等。

6.高斯函数。

初等数论是一个理论层次

第一个层次叫做数学概念，是反映对象的本质属性的思维形式。人类在认识过程中，从感性认识上升到理性认识，把所感知的事物的共同本质特点抽象出来，加以概括，就成为概念。表达概念的语言形式是词或词组。科学概念，特别是数学概念要求更加严格，至少必须具备三个条件：专一性，精确性，可以检验。例如：”孪生素数猜想“就是一个数学概念。

第二个层次叫做数学命题，数学命题是对一系列数学概念之间的关系作出判断的句子。一个命题要么真，要么不真（这由逻辑中的排中律保证）。真命题包含定理，引理，推论，事实等。命题既可以是存在性命题（表述为”存在......."），也可以是全称命题（表述为“对于一切....."）。

第三个层次叫做数学理论，把方法，公式，公理，定理，原理，组合成为一个体系叫做数学理论。例如“初等数论”，由公理（例如等量公理），定理（例如费马小定理），原理（例如抽屉原理，一一对应原理），公式等组成。

在数学证明时，全称命题常常不能通过枚举法来判断真伪，这是因为数学有时面对的是无穷多个对象，永远不可能一一枚举出每一种情况。不完全归纳法在数学中是不可行的，数学只承认演绎逻辑（数学归纳法，超限归纳法等均属于演绎逻辑）。

费马

皮耶·德·费玛在古典数论领域中的成果很多，比如提出了不定方程无解证明的无穷递降法，引入了费马数等等。

与费马相关的著名结论如下：

费马小定理：，其中p是一个素数，a是正整数。

事实上它是欧拉定理的一个特殊情况，Euler定理是说：,a，n都是正整数且互素，φ(n)是Euler函数，表示和n互素的小于n的正整数的个数。

费马大定理（当时是猜想）：是整数，则方程没有满足的整数解。这个是不定方程，它已经由美国数学家安德鲁·怀尔斯证明了(1995年)，证明的过程相当艰深。

引入欧拉函数，得到著名的欧拉定理——费马小定理推广；研究了连分数展开问题；用解析方法证明了素数无限；讨论平方和问题及哥德巴赫猜想——加性数论内容。

高斯

被誉为“数学王子”。解决了正多边形尺规作图问题，将它和费马数联系起来。高斯的着作

《算术研究》提出了同余理论，讨论了平方剩余问题，发现了二次互反律。高斯提出了著名的素数定理（当时是猜想），研究了指标和估计问题——表示论的雏形。

高等学校数学教材初等数论（第二版）定价：￥35.00

作者：潘承洞，潘承彪着

出 版 社：北京大学出版社有限公司

出版时间：2003-1-1

版次：2

页数：592

字数：520000

印刷时间：2011-1-1

开本：大32开

纸张：胶版纸

印次：9

I S B N：9787301060759

包装：平装

内容简介

本书自1992年9月出版以来，已发行24000册，深受教师和学生的欢迎。在第二版中，本书作者根据10年来读者和本书编辑提出的宝贵意见，以及在教学实践中的体会，对本书内容做了进一步修改与完善（见第二版说明），使之更适宜于教学需要。

本书是大学初等数论课教材。全书共分九章。内容包括：整除，不定方程，同余，同余方程，指数与原根，连分数，素数分布的初等结果，数论函数等。书中配有较多的习题，书末附有提示与解答。?书积累了作者数十年教学与科研的经验，遵循少而精的原则，精心选材。为便于学生理想，对重点内容多侧面分析，从不同角度进行阐述。

作者简介潘承洞，数学家，中科院院士。江苏苏州人。着作有《哥德巴赫猜想》（合着）、《阶的估计》等。

目录第二版说明

第一版序

符号说明

第一章整除

1自然数与整数

2整除

3带余数除法与辗转相除法

4最大公约数理论

5算术基本定理（A）

6算术基本定理（B）

7符号的分解式

8容斥原理与的计算公式

第二章不定方程（I）

1一次不定方程

第三章同余

1同余

2同余类与剩余系

3（M）的性质与Fermat-Euler定理

4Wlison定理

第四章同余方程

1同余方程的基本概念

2一次同余方程

3一次同余方程组，中国剩余定理

4一般同余方程的求解

5横为素数的二次同余方程

6Legendre符号,Gauss二次互反律

7Jacbi符号

8模为素数的高次同余方程

9多元同余方程,Chevalley定理

第五章指数与原根

1指数

2原根

3指标、指？组与既约剩余系的构造

4二项同余方程

第六章不定方程（II）

……

第七章连分数

第八章素数分布的初等结果

第九章数论函数

附录一自然数

附录二算术基本定理不成立的例子

附录三初等数论的几个应用

附录四国际数学奥林匹克竞赛中数论有关的题

习题的提示与解答