石大《初等数论》课件

初等数论序言篇

数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除理论、同余理论为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（elementarynumbertheory）。

初等数论的大部分内容早在古希

腊欧几里德的《

几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，

即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。

近代初等数论的发展得益于费

马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。高斯还提出：“数学是科学之王，数论是数学之王”。可见高斯对数论的高度评价。

欧几里德高斯

欧拉费马

拉格朗日毕达格拉斯

数论的分支

由于自20世纪以来引进了抽象代数和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时促进着数论的发展。带余(数)除法

设a、b是两个给定的整数，其中b>0，那么，一定存在惟一的一对整数q及r，满足

a=bq+r

，0≤r<b

可以看出：b整除a的充要条件是r=0。我们称r是以b除a的余数。带余除法可以用下面的数轴表示带余除法的关注点带余除法中的商实际上为（不超过

的最大整数），余数为。而带余除法的核心是关于余数r的不等式：。

第一篇整数的p进位制及其应用

正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。

正整数的p进制表示

正整数A的p进制表示：

实用进制在计数和运算中，我们常常采用“逢十进一”，这种计数的方法称为“十进制”，10称为“基数”。十进制中，用0，1，2，…，9这十个数码就可以表示所有的数字，同一数码在不同的位置上意义不同。而计算机使用“二进制”来处理各种信息,二进制是“逢二进一”，只用两个数码0和1来表示所有的整数。二进制转为十进制任意一个二进制表示的数其中或1（0≤j≤n），等于转换为十进制为：

十进制转为二进制以11为例，按照下面的方法转换：11=11余数

5………1＝a02………1＝a11………0＝a20………1＝a32222低位高位同一数值的不同进制表示

对于任何一个数，可以用不同的进位制来表示。比如：十进制数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。生活中的进位制二进制广泛用于计算机三进制用于军队编制十进制最常用十二进制如时辰、月份、一打物品十六进制广泛用于计算机六十进制如秒、分,角度等进制的文化

世界上各个民族用各种各样的记数法来组织他们的数。古代玛雅人和古日耳曼民族曾采用二十进位制；我国在计量方面曾采用十六进制（1斤＝16两）；在澳洲和非洲的最原始的民族中，还存在着一种计数法，是以二为基底的二进制；古老的巴比伦的六十进位制，至今仍被天文学家所利用，在角度和时间的分秒计算中，我们仍然采用这种进位制；另外还有十二进制、五进制等。第二篇整数的整除性

整数的整除理论是初等数论的基础，其中心内容是最大公因数与最小公倍数理论，最基本、最重要的结果是算术基本定理。带余除法是建立整数的整除理论的一个重要工具。

辗转相除法（也称Euclid算法）是初等数论中最重要的方法之一，它由有限次带余除法构成，利用它不仅可以证明最大公因数的如下重要性质：

（a,b）=ax+by，

还可以给出最大公因数（a,b）和x,y的有效算法。

算术基本定理是初等数论的基石，它表明素数是正整数最基本的构成单位。

整数的基本整除性质

数的整除的特征（1）末位数字是0，2，4，6，8的整数都能被2整除；（2）末位数字是0或5的整数必被5整除；（3）末两位数字组成的两位数能被4（或25）整除的整数必被4（或25）整除；（4）末三位数字组成的三位数能被8（或125）整除的整数必被8（或125）整除；（5）各个数位上数字之和能被3（或9）整除的整数必被3（或9）整除；

（6）将一个多位数从个位起往前三位一组进行分段，奇数段各三位数之和与偶数段各三位数之和的差若被7（11或13）整除，则原多位数也能被7（11或13）整除；事实上，（7）n个连续整数中，有且只有一个是n的倍数；（8）任何n个连续的整数之积一定是n!的倍数。

------问题？1一个31位数，如果把这个整数的每相邻的两个数码组成的整数作为两位数来考虑的话，任何一个这样的两位数都可以被17或23整除。另外，这个31位数的数码中只有一个7，求这个31位数的所有数码之和，并写出思考过程。2一张数学试卷只有25道选择题，做对1道题得4分，做错1道题扣1分，如果不做，不得分也不扣分。若某位同学得了78分，那么他做对

道题，做错

道题，不做

道题。参考解答：14692346923469234692346923468517

这一31位数的所有数码之和为（9+2+3+4+6）5+4+6+8+5+1+7=151.其实，17的两位数倍数是17，34，51，68，及85；23的两位数倍数是23，46，69及92.2

依据得分规则和关键数据78来分析判断。

由2|78而4├78，可知做错的题数是2的倍数而不是4的倍数。若答错2道题，则做对的题数为，不做的题数为3，合题意。若做错6道或6道以上，则至少做对21道，此时6+21=27>25，不合题意！质数与合数一个大于1的正整数，如果它的正因数只有1和它本身，就叫作质数（或素数），否则就叫做合数。

“1”既不是质数也不是合数。（1）算术基本定理：任何一个大于1的整数都可以分解成质数的乘积。如果不考虑这些质因子的次序，则这种分解法是唯一的。（2）设n是大于2的整数，如果不大于的质数都不是n的因子，则n是质数。

即对任一整数a＞1，有a＝，其中p1＜p2＜…＜pn均为质数，1、2、…、n都是正整数。质（素）数的基本性质

实用、常用------问题？1判断391，827是合数还是质数。解：391<400=,20以内的质数有2，3，5，7，11，13，17，19.根据2，3，5，7，11整除的数的特征，易知它们都不是391的因数，经试验，39117=23，故391是合数。再827<=841,29以内的质数有2，3，5，7，11，13，17，19,23.这9个质数都不能整除827，故827是质数。（先找一个比A大且最接近A的平方数，再写出N以内的所有质数，如果这些质数都不能整除A,那么A是质数；否则A为合数。）

2判断2n+1位整数是质数还是合数？解：由这个数的各个数位上数字之和为

2n+3+n=3(n+1),可知这一数能被3

整除，所以这一数是合数。另：将“3”拆开原数==

=于是知原数是合数。最大公因数与辗转相除法

设a,b是两个整数，若整数d是它们所有公因数中最大的一个，则称d为它们的最大公因数，记作d=(a,b)。特别地，当(a,b)＝1时，称a,b为互素。对于三个不全为零的整数a,b,c来说，若a=bq+c其中q是非零整数，则a,b与b,c有相同的公因数，因而(a,b)=(b,c)本节介绍一个计算最大公因数的算法——辗转相除法，又称Euclid算法，它是数论中的一个重要方法。辗转相除法给定两个正整数，用带余除法得到下面的k+1个等式…………

…………不难看出定义1整数的公共因数称为

的公约数。

不全为零的整数的公因数中最大的一个叫做的最大公因数（或最大公约数），记为。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。

------问题？将长60厘米，宽24厘米的长方形纸片，裁成同样大小且边长是整数厘米的正方形纸片，并且没有剩余，一共有多少种裁法？若要正方形纸片尽可能大，那么可以裁成多少张正方形纸片？1至1000之间的自然数中能同时被2，3，5整除的数共有多少个？（33个）满足被3除余1，被4除余2，被5除余3，被6除余4的最小自然数是

58

。参考解答：

1

解：（60，24）=12（5，2）=12=

由12的因数个数为（2+1）（1+1）=6，知有12种不同的裁法。正方形最大时裁成的张数为。

2

分析：能同时被2，3，5整除的数是2，3，5的公倍数，又2，3，5的公倍数是其最小公倍数的倍数，由此问题转化为求1至1000的自然数中有多少个数是2，3，5的最小公倍数的倍数。[2,3,5]=30,100030=33......10。

3解：[3,4

,5]

-2=58。

算术基本定理

任一大于1的整数a能表成素数的乘积：

（1）其中是素数。且在不计次序的意义下，表示式（1）是惟一的。算术基本定理的证明第三篇不定方程

所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些限制（如要求是有理数、

整数或正整数等等）的方程或方程组。不定方程也称为丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。不定方程的重要性在数学竞赛中也得到了充分的体现，每年世界各地的数学竞赛中，不定方程都占有一席之地；另外它也是培养学生思维能力的好材料，数学竞赛中的不定方程问题，不仅要求学生对初等数论的一般理论、方法有一定的了解，而且更需要讲究思想、方法与技巧，创造性的解决问题。

二元一次不定方程的整数解第四篇整数的同余性