序言
数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（Elementary Number Theory）。
初等数论的大部份内容早在古希腊欧几里德的《 几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法， 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。
近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。 “数学是科学之王，数论是数学之王”。 -----高斯
由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用，无疑同时间促进着数论的发展。 数论是以严格和简洁著称，内容既丰富又深刻。我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过的一些基本概念，例如整除性、最大公因子、最小公倍数、辗转相除法等，有较深入的了解。
第一章 整数的整除性
§1.1整除的概念
一、基本概念
1、自然数、整数 2、正整数、负整数 3、奇数、偶数 一个性质：
整数+整数=整数 整数-整数=整数 整数*整数=整数
二、整除
1、定义：设a，b是整数，b≠0。如果存在一个整数q使得等式： a=bq
成立，则称b能整除a或a能被b整除，记作 b∣a；如果这样的q不存在，则称b不能整除a。
2、整除的性质
（1）如果b∣a， c∣b，则c∣a. （2）如果b∣a，则cb∣ca.
（3）如果c∣a，则对任何整数d， c∣da.
（4）如果c∣a， c∣b，则对任意整数m，n，有 c∣ma+nb.
（5）如果a∣b， b∣a，则a=±b.
3、质数、合数
质数（素数）是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除（除0以外）
的数称之为素数（质数）。 合数 ：比1大但不是素数的数称为合数，1和0既非素数也非合数。 质因数 ：质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。每个合数都可以写成几个质数（也可称为素数）相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。 分解质因数 ：任何一个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。分解质因数只针对合数。 算术基本定理： 任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 , 这里P1 定理： 设a，b是两个整数，其中b＞0，则存在两个唯一的整数q及r，使得 a=bq+r，0?r＜b 成立.我们称r是b除a的余数。 可以看出：b整除a的充要条件是r=0。 §1.2最大公因数和辗转相除法 一、最大公因数 1、定义 设a1，a2，?，an是n个不全为零的整数，若整数d是它们之中每一个的因数，那么d就叫做a1，a2，?，an的一个公因数。整数的公因数中最大的一个叫做它们的最大公因数，记作（a1，a2，?，an） 。 2、互质 设a1，a2，?，an是n个不全为零的整数，若 （a1，a2，?，an） =1， 则称a1，a2，?，an 是互质的。 注：三个互质比一定两两互质。 比如（3，4，6）=1，但（3，6）=3，（4，6）=2. 3、最大公因数的性质 （1）当b∣a时，（a，b）=b. （2）a，b的一切公因数都是（a，b）的因数. （3）若a，b是正整数，m是任一正整数，则有 （am，bm）=（a，b）m. （4）若（a，b）=1，c为任一正整数，则有 （ac，b）=（c，b） （5）若（a，b）=1， b∣ac，则有b∣c. (ab,)?1dd （6）若a，b，c是任意三个正整数，则（a，b）=d的充分必要条件是：4、辗转相除法 1、定理： 设a,b是任意两个正整数，且a＞b，且有 a?bq?r, 0＜r＜b， 其中q，r都是正整数，则有 (a,b)?(b,r) 2、辗转相除法 定理： 若a,b是任意两个正整数，且a＞b，由带余除法，有下列等式 a?bq?r, 0＜r＜b， b?rq1?r1, 0＜r1＜r， r?r1q2?r2, 0＜r2＜r1， … … rn?2?rn?1qn?rn, 0＜rn＜rn?1， rn?1?rnqn?1?rn?1, rn?1?0, 则有(a,b)?rn. 一个推论 若a，b是正整数，且（a，b）=d，则必存在整数m和n，使得 d=ma+nb 注：证明可由带余除法逆向代入证得。