10=5×2 所以（2605，3245，7250）= （295，7250）=5.
练习
求（125，610）. 求（51306，1224）. 求（538，244，555）.
§1.3最小公倍数 一、定义
设 a1,a2,a3,..., an 是 n 个不全为零的整数， 若整数 m 是它们之中每一个的倍数，那 么 m 就叫做 a1,a2,a3,..., an 的一个公倍数。整
二、整除
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，有
例2：求×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，
初等数论的大部份内容早在古希腊欧 几里德的《 几何原本》中就已出现。欧几 里得证明了素数有无穷多个，他还给出求 两个自然数的最大公约数的方法， 即所谓 欧几里得算法。我国古代在数论方面亦有 杰出之贡献，现在一般数论书中的“中国 剩余定理”正是我国古代《孙子算经》中
的下卷第26题，我国称之为“孙子定理”。
（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是任一正整数，则有
r r1q2 r2 ,
…
…
0＜ r2 ＜ r1 ，
rn2 rn1qn rn , 0＜ rn ＜ rn1 ，
rn1 rn qn1 rn1 , rn 1 0 ,
一个推论
若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.
c∣ma+nb.
（5）如果a∣b， b∣a，则a=±b.
3、质数、合数
质数（素数） 合数 质因数 分解质因数 算术基本定理
4、带余除法
定理： 设a，b是两个整数，其中b＞0，则存
在两个唯一的整数q及r，使得 a=bq+r，0≤r＜b
成立.我们称r是b除a的余数。 可以看出：b整除a的充要条件是r=0。
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
§1.2最大公因数和辗转相除法
一、最大公因数
1、定义 设a1，a2，…，an是n个不全为零的整数，若整
数d是它们之中每一个的因数，那么d就叫做 a1，a2，…，an的一个公因数。整数的公因数中 最大的一个叫做它们的最大公因数，记作
（a1，a2，…，an） 。
2、互质
设a1，a2，…，an是n个不全为零 的整数，若
（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的充分必要条件是：
(a ,b) 1 dd
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 ，
则有 (a,b) rn .
近代初等数论的发展得益于 费马、欧拉、拉格朗日、勒让德 和高斯等人的工作。1801年，高 斯的《算术探究》是数论的划时 代杰作。
“数学是科学之王，数论是数 学之王”。 -----高斯
欧几里德
高斯
费马
欧拉
拉格朗日
毕达格拉斯
由于自20世纪以来引进了抽象数学和高 等分析的巧妙工具，数论得到进一步的发 展，从而开阔了新的研究领域，出现了代 数数论、解析数论、几何数论等 新分支。 而且近年来初等数论在计算器科学、组合 数学、密码学、代数编码、计算方法等领 域内更得到了 广泛的应用，无疑同时间
大学数学
初等数论 线性代数 射影几何 概率统计
初等数论
赵争 Email:
序言
数论是研究整数性质的一门很 古老的数学分支， 其初等部分是以
整数的整除性为中心的，包括整除性、 不定方程、同余式、连分数、素数 （即整数）分布 以及数论函数等内 容，统称初等数论（Elementary Number Theory）。
促进着数论的发展。
数论是以严格和简洁著称， 内容既丰富又深刻。我将会介绍数论中 最基本的概念和理论，希望大家能对这 门学问产生兴趣，并且对中小学时代学 习过的一些基本概念，例如整除性、最 大公因子、最小公倍数、辗转相除法等， 有较深入的了解。
第一章 整数的整除性
§1.1整除的概念
一、基本概念
1、自然数、整数 2、正整数、负整数 3、奇数、偶数 一个性质： 整数+整数=整数 整数-整数=整数 整数*整数=整数