序言
数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（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<P2<...<Pn是质数，其诸方幂 ai 是正整数。
4、带余除法
定理：
设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.
（6）若a，b，c是任意三个正整数，则（a，b）=d的充分必要条件是：
4、辗转相除法
一个推论
若a，b是正整数，且（a，b）=d，则必存在整数m和n，使得
d=ma+nb
注：证明可由带余除法逆向代入证得。
例1：求（735000，238948）.
解：因为735000=238948×3+18156，
238948=18156×13+2920
18156=2920×6+636
2920=636×4+376
636=376×1+260
376=260×1+116
260=116×2+28
116=28×4+4
28=4×7
所以（735000，238948）=4.
例2：求（2605，-5125）.
解：因为5125=2605×1+2520，
2605=2520×1+85
2520=85×29+55
85=55×1+30
55=30×1+25
30=25×1+5
25=5×5
所以（2605，-5125）=5.
例3：求（2605，3245，7250）.
解：先求2065和3245的最大公因数。
因为3245=2605×1+1180，
2605=1180×1+885
1180=885×1+295
885=295×3
所以（2605，3245）=295.
再求295与7250的最大公因数。
7250=295×24+170，
295=170×1+125
170=125×1+45
125=45×2+35
45=35×1+10
35=10×3+5
10=5×2
所以（2605，3245，7250）= （295，7250）=5.
练习
求（125，610）.
求（51306，1224）.
求（538，244，555）.
§1.3最小公倍数
一、定义
二、最小公倍数的性质
1、定理：
例1：求[3468,24871].
解：由辗转相除法得：
（3468，24871）=17.
所以[3468,24871]= 
=5073684.
例2：求[128，234，524].
习题
1、求[21，35].
2、求[123，321].
3、求[125，725，1125，2015].
§1.4整数可除性的检验
一、整数的表示
1、十进制的整数的意义：各位数字的加权和。
2、一般表示：
进位制
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。
进位制
常见的进位制：
二进制广泛用于计算机
三进制用于军队编制
十进制最常用
十二进制时辰、月份、一打物品
十六进制广泛用于计算机
六十进制秒、分,角度
二、可除性判别方法
判别方法1：（整数被2整除）
如果一个整数的末尾数字能被2整除，则该数能被2整除。即：若2∣a0，，则2 ∣N.
判别方法2：（整数被5整除）
如果一个整数的末尾数字能被5整除，则该数能被5整除。即：若5∣a0，，则5∣N.
判别方法3：（整数被3整除）
如果一个整数的各位数字之和能被3整除，则该数能被3整除。即：若3∣an+an-1+…a1+a0，，则3 ∣N.
判别方法4：（整数被9整除）
如果一个整数的各位数字之和能被9整除，则该数能被9整除。即：若9∣an+an-1+…a1+a0，，则9 ∣N.
二、可除性判别方法
判别方法5：（整数被11整除）
如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果
，则11︱N.
判别方法6：（整数被13整除）
如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果
，则13︱N.
第二章 不定方程
§2.1二元一次不定方程
一、齐次方程
二、非齐次方程
例1
三、有整数解的充要条件
两个推论
推论1：
如果（a，b）=1，那么方程（1）有整数解.
推论2：
如果（a，b）∣c，那么方程（1）没有整数解.
例2：判断下列不定方程有没有整数解。
四、整数分离法解不定方程
步骤：1、把不定方程变形，用系数绝对值较大的未知数表示系数绝对值较小的未知数；
2、把1中的代数式分离成一个整式和一个分式之和；
3、通过观察和其它方法使分式值为整数从而筛选得到不定方程的整数解。
例3
例4:解下列不定方程
五、不定方程组
例2：求解不定方程组
习题
§2.2多元一次不定方程
一、三元一次不定方程
1、解的存在性
定理：三元一次不定方程
ax+by+cz=d
有整数解的充分必要条件是（a，b，c) ∣d，
其中a，b，c，d都是正整数.
2、三元一次不定方程的通解
一般解法
第三章 同余
§3.1同余的概念和性质
二、同余的性质
定理 同余关系是等价关系，即
(1)自反性 a≡a(mod m)。
(2)对称性 若a≡b(mod m)，则b≡a(mod m)。
(3)传递性 若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)。
定理 设a、b、c、d为整数，m为正整数，若a≡b(mod m)，
c≡d(mod m)，则：
(1)ax＋cy≡bx＋dy(mod m)，x、y为任意整数，即同余式可以相加；
(2)ac≡bd(mod m)，即同余式可以相乘；
(3)an≡bn(mod m)，n＞0；
(4)f(a)≡f(b)(mod m)，f(x)为任一整系数多项式。
证明 (1)因为a≡b(mod m)，c≡d(mod m)，所以m|(a－b)，m|(c－d)，于是m|((a－b)x＋(c－d)y)，即m|((ax＋cy)－(bx＋dy))，故ax＋cy≡bx＋dy(mod m)。
(2)因为a≡b(mod m)，c≡d(mod m)，所以m|(a－b)，m|(c－d)，于是m|((a－b)c＋(c－d)b)，即m|(ac－bd)，故ac≡bd(mod m)。
(3)因为a≡b(mod m)，则存在整数q使得a－b＝mq。于是：
an－bn＝(b＋mq)n－bn＝(bn＋bn-1(mq)1＋…＋b1(mq)n-1＋(mq)n)－bn＝mp，其中p是一整数。 所以an≡bn(mod m)。
(4)由(1)和(3)可证。
定理 若ac≡bc(mod m)，且(c，m)＝d，则a≡b(mod m/d)
证明 由(c，m)＝d得(c/d，m/d)＝1。由ac≡bc(mod m)得m|(ac－bc)，于是(m/d)|(a－b)(c/d)。又(c/d，m/d)＝1，从而(m/d)|(a－b)。故a≡b(mod m/d)。
例1 求3406写成十进制数时的个位数。
解 因为32≡－1(mod 10)，34≡1(mod 10)，所以3404≡1(mod 10)。因此，3406≡3404·32≡9(mod 10)。所以个位数为9。
例2：求使2n+1能被3整除的一切自然数n.
孙子定理和大衍求一术
