大学数学大学数学初等数论线性代数射影几何概率统计1初等数论初等数论赵争赵争Email:zhaozjssvc.edu.cnEmail:zhaozjssvc.edu.cn2序言序言 3 数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（Elementary Number Theory）。 4 初等数论的大部份内容早在古希腊欧几里德的 几何原本中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法， 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代孙子算经中的下卷第26题，我国称之为“孙子定理”。 5 近代初等数论的发展得益于近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德费马、欧拉、拉格朗日、勒让德和高斯等人的工作。和高斯等人的工作。18011801年，高年，高斯的斯的算术探究算术探究是数论的划时是数论的划时代杰作。代杰作。 “数学是科学之王，数论是数学是科学之王，数论是数学之王数学之王”。 -高斯高斯6 数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（Elementary Number Theory）。 7 初等数论的大部份内容早在古希腊欧几里德的 几何原本中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法， 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代孙子算经中的下卷第26题，我国称之为“孙子定理”。 8 近代初等数论的发展得益于近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德费马、欧拉、拉格朗日、勒让德和高斯等人的工作。和高斯等人的工作。18011801年，高年，高斯的斯的算术探究算术探究是数论的划时是数论的划时代杰作。代杰作。 “数学是科学之王，数论是数学是科学之王，数论是数学之王数学之王”。 -高斯高斯9 欧几里德欧几里德 高斯高斯10费马费马欧拉欧拉11拉格朗日拉格朗日 毕达格拉斯毕达格拉斯12 由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用，无疑同时间促进着数论的发展。 13 数论是以严格和简洁著称，内容既丰富又深刻。我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过的一些基本概念，例如整除性、最大公因子、最小公倍数、辗转相除法等，有较深入的了解。14第一章 整数的整除性1.1整除的概念一、基本概念 1、自然数、整数 2、正整数、负整数 3、奇数、偶数一个性质： 整数+整数=整数 整数-整数=整数 整数*整数=整数 15二、整除1、定义：设a，b是整数，b0。如果存在一个整数q使得等式： a=bq 成立，则称b能整除a或a能被b整除，记作 ba；如果这样的q不存在，则称b不能整除a。162、整除的性质 （1）如果ba， cb，则ca. （2）如果ba，则cbca. （3）如果ca，则对任何整数d， cda. （4）如果ca， cb，则对任意整数m，n，有 cma+nb. （5）如果ab， ba，则a=b.173、质数、合数质数（素数）合数质因数分解质因数算术基本定理184、带余除法定理： 设a，b是两个整数，其中b0，则存在两个唯一的整数q及r，使得 a=bq+r，0rb 成立.我们称r是b除a的余数。 可以看出：b整除a的充要条件是r=0。191.2最大公因数和辗转相除法一、最大公因数 1、定义 设a1，a2，an是n个不全为零的整数，若整数d是它们之中每一个的因数，那么d就叫做a1，a2，an的一个公因数。整数的公因数中最大的一个叫做它们的最大公因数，记作 （a1，a2，an） 。202、互质 设a1，a2，an是n个不全为零的整数，若 （a1，a2，an） =1， 则称a1，a2，an 是互质的。注：三个互质比一定两两互质。比如（3，4，6）=1，但（3，6）=3，（4，6）=2.213、最大公因数的性质（1）当ba时，（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， bac，则有bc.（6）若a，b，c是任意三个正整数，则（a，b）=d的充分必要条件是：224、辗转相除法2324一个推论 若a，b是正整数，且（a，b）=d，则必存在整数m和n，使得 d=ma+nb注：证明可由带余除法逆向代入证得。25例1：求（735000，238948）.解：因为735000=2389483+18156， 238948=1815613+2920 18156=29206+636 2920=6364+376 636=3761+260 376=2601+116 260=1162+28 116=284+4 28=47所以（735000，238948）=4.26例2：求（2605，-5125）.解：因为5125=26051+2520， 2605=25201+85 2520=8529+55 85=551+30 55=301+25 30=251+5 25=55所以（2605，-5125）=5.27例3：求（2605，3245，7250）.解：先求2065和3245的最大公因数。 因为3245=26051+1180， 2605=11801+885 1180=8851+295 885=2953 所以（2605，3245）=295. 再求295与7250的最大公因数。 7250=29524+170， 295=1701+125 170=1251+45 125=452+35 45=351+10 35=103+5 10=52所以（2605，3245，7250）= （295，7250）=5.28练习求（125，610）.求（51306，1224）.求（538，244，555）.291.3最小公倍数一、定义30二、最小公倍数的性质1、定理：3132例1：求3468,24871.解：由辗转相除法得： （3468，24871）=17.所以3468,24871= =5073684.33例2：求128，234，524.34习题1、求21，35.2、求123，321.3、求125，725，1125，2015.351.4整数可除性的检验一、整数的表示1、十进制的整数的意义：各位数字的加权和。2、一般表示：36进位制 进位制进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。 37进位制进位制 常见的进位制：常见的进位制： 二进制广泛用于计算机二进制广泛用于计算机 三进制用于军队编制三进制用于军队编制 十进制最常用十进制最常用 十二进制时辰、月份、一打物品十二进制时辰、月份、一打物品 十六进制广泛用于计算机十六进制广泛用于计算机 六十进制六十进制秒、分秒、分,角度角度 38二、可除性判别方法判别方法1：（整数被2整除） 如果一个整数的末尾数字能被2整除，则该数能被2整除。即：若2a0，则2 N.判别方法2：（整数被5整除） 如果一个整数的末尾数字能被5整除，则该数能被5整除。即：若5a0，则5N.判别方法3：（整数被3整除） 如果一个整数的各位数字之和能被3整除，则该数能被3整除。即：若3an+an-1+a1+a0，则3 N.判别方法4：（整数被9整除）如果一个整数的各位数字之和能被9整除，则该数能被9整除。即：若9an+an-1+a1+a0，则9 N.39二、可除性判别方法判别方法5：（整数被11整除） 如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果 ，则11N.判别方法6：（整数被13整除） 如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果 ，则13N.40第二章 不定方程412.1二元一次不定方程一、齐次方程42二、非齐次方程43例144三、有整数解的充要条件45两个推论推论1： 如果（a，b）=1，那么方程（1）有整数解.推论2： 如果（a，b）c，那么方程（1）没有整数解.46例2：判断下列不定方程有没有整数解。47四、整数分离法解不定方程步骤：1、把不定方程变形，用系数绝对值较大的未知数表示系数绝对值较小的未知数；2、把1中的代数式分离成一个整式和一个分式之和；3、通过观察和其它方法使分式值为整数从而筛选得到不定方程的整数解。48例349例4:解下列不定方程50五、不定方程组5152例2：求解不定方程组53习题542.2多元一次不定方程一、三元一次不定方程1、解的存在性 定理：三元一次不定方程 ax+by+cz=d有整数解的充分必要条件是（a，b，c) d，其中a，b，c，d都是正整数. 552、三元一次不定方程的通解56一般解法57第三章 同余3.1同余的概念和性质58二、同余的性质5960定理定理 同余关系是等价关系，即(1)自反性 aa(mod m)。(2)对称性 若ab(mod m)，则ba(mod m)。(3)传递性 若ab(mod m)，bc(mod m)，则ac(mod m)。61定理定理 设a、b、c、d为整数，m为正整数，若ab(mod m)，cd(mod m)，则： (1)axcybxdy(mod m)，x、y为任意整数，即同余式可以相加；(2)acbd(mod m)，即同余式可以相乘；(3)anbn(mod m)，n0；(4)f(a)f(b)(mod m)，f(x)为任一整系数多项式。证明证明 (1)因为ab(mod m)，cd(mod m)，所以m|(ab)，m|(cd)，于是m|(ab)x(cd)y)，即m|(axcy)(bxdy)，故axcybxdy(mod m)。(2)因为ab(mod m)，cd(mod m)，所以m|(ab)，m|(cd)，于是m|(ab)c(cd)b)，即m|(acbd)，故acbd(mod m)。62(3)因为ab(mod m)，则存在整数q使得abmq。于是：anbn(bmq)nbn(bnbn-1(mq)1b1(mq)n-1(mq)n)bnmp，其中p是一整数。所以anbn(mod m)。(4)由(1)和(3)可证。63定理定理 若acbc(mod m)，且(c，m)d，则ab(mod m/d)证明证明 由(c，m)d得(c/d，m/d)1。由acbc(mod m)得m|(acbc)，于是(m/d)|(ab)(c/d)。又(c/d，m/d)1，从而(m/d)|(ab)。故ab(mod m/d)。64例例1 1 求3406写成十进制数时的个位数。解解 因为321(mod 10)，341(mod 10)，所以34041(mod 10)。因此，34063404329(mod 10)。所以个位数为9。65例2：求使2n+1能被3整除的一切自然数n.6667孙子定理和大衍求一术6869