初等数论单元复习课件

单元小结,第一章 整数的整除性,定义1.1 设 a，b Z ，b0，如果存在 q Z ，使得等式 abq成立我们就说，a能被b整除或b整除a ，记作b | a 如果整数 q 不存在( 即对任何整数 q，恒有bq a ),那么就说a不能被 b 整除 (或者说b不能整除a)，记作 b a。,1.1整除 1、整除的概念：,如果整数 a 能被整数b (b 0) 整除(即b | a)， 那么 a就叫做 b 的倍数，b就叫做a的约数.,2、当然约数与真约数:一般地，在整数a的约数中 l与a叫做整数a的当然约数；除1与a之外，a的其它约数叫做a的真约数(或非当然约数)。,(5) x, y为任意整数，若 a b , a c , 则a (bx+cy)；,(6) 若 m0, 则a b 的充分必要条件是ma m b,(7) 若a b , b a，则 a = b,(8) 若 a ，b N+, a b , 则a b,(9) 若a是b的真约数，则1 a b ,4、整除的基本性质:,4、带余除法,设a, b是两个整数，b 0，则一定有并且只有两个整数 q , r 使得 a= bq + r,0rb 成立，而且q与r是唯一的 求两个数的不完全商q和余数的运算叫做带余除法运算(或有余数除法运算),1、奇数与偶数的定义: 根据整除概念我们把能被2整除的整数叫做偶数，不能被2整除的整数叫做奇数，它们的一般表示式为： 偶数N=2n(n为整数)，奇数N2n+l(n为整数),二、 奇数与偶数,2、奇数与偶数具有下面性质：,性质1 (关于偶数) (1) 任意个偶数的和(或差)是偶数； (2) 任意一个整数与偶数的积是偶数， 特别地，n 个偶数的积是 2n 的倍数（ nN+）.,性质2 (关于奇数),(1) 双数个奇数的和是偶数； (2) 单数个奇数的和是奇数； (3) 任意个奇数的积还是奇数。 性质3 奇数与偶数的和是奇数. 性质4 任一奇数与任一偶数不相等.,1.2最大公约数与最小公倍数 1. 最大公约数： 一般地，n个整数的公有的约数，叫做这n个数的公约数，n个数的公约数中最大的一个数，叫做这n个数的最大公约数 整数a1 ,a2, ,an(n2，nN)的最大公约数用符号(a1 ,a2 , ,an)来表示 如果两个整数的最大公约数是1，那么这两个数叫做互质数，或者说，这两个数互质,（3）n 个数互质,若(a1 ，a2 ， ，an) =1, 那么就叫做这 n 个数互质 例如，(2，4，9)1，我们就说2，4，9这三个数互质,如果 a1 ，a2 ， ，an ( n2) 中的任意两个数 ai, aj ( i j, I 1, 2, , n；j 1, 2, , n) 互质，即 (ai, aj ) 1，那么就叫做这 n 个整数两两互质,（4）n 个数两两互质,设a，b为两个任意自然数,ab，如果 abq1+r1 (0r1b)， br1q2+r2 (0r2r1)， r1r2q3+r3 (0r3r2)， rn-3rn-2qn-1+rn-1 (0rn-1rn-2)， rn-2rn-1qn+rn (0rnrn-1)， rn-1rnqn+1, 那么 (a，b)rn,辗转相除法,例：试求377与319的最大公约数,解 由377除以319，得 377319 158，由319除以58，得 31958 5 29， 由58除以29，得 5829 2 由定理19的推论可知，最后一个不为 零的余数就是377与319的最大公约数，即 (377，319)29,性质：定理1.3.3推论1(裴蜀恒等式) 如果两个数a，b的最大公约数是d，那么存在两个整数x与y，使得等式ax+byd成立(可以推广到n个数的情况) 推论2：两个数a，b互质的必要且充分条件是存在整数x与y,使axby1成立。,推论1的推广,设 a1 ,a2 , , an N+ (n2) ，则一定存在整数 s1, s2, , sn，使 a1s1a2s2 ansn (a1 ,a2 , ,an ) .,2. 最小公倍数 意义：n个整数公有的倍数，叫做这n个数的公倍数，n个整数的非零公倍数中最小的正数叫做这n个数的最小公倍数自然数a1, a2 , ,an (n2，nN)的最小公倍数，用符号 a1, a2 , ,an 表示 性质：）n 个数的最小公倍数能整除它们的任何一个公倍数，就是如果 d=a1,a2 , ,an ，D是a1, a2 , ,an的任意一个公倍数，那么 d |D,2)两个数的最大公约数与最小公倍数的积等于这两个数的积，就是(a，b) a，b =a b 推论 若(a,b)=1，则a,b=ab,定理1.3.8与定理1.3.9 可类比定理1.3.6与定理1.3.7 得到。,定理1. 3. 6 (a1，a2，ak) = d的充要条件是,最大公约数与最小公倍数的其他性质,多个数的最大公约数和最小公倍数,定理1.3.10,定理1.3.11,由此表明，多个数的最大公约数、最小公倍数可以由求两个数的最大公约数与最小公倍数逐步求出,定理1.3.13 若a | bc, 且 (a, b) =1, 则 a | c.,定理1.3.14 若 (a, b)=1, 则 (a, bc) = (a, c).,我喜欢数学,互质的性质,定理1.3.15 若a | c, b | c, (a, b)=1, 则 ab | c.,1.3质数与合数 算术基本定理 1. (1) 质数(素数)：一个大于1的自然数，如果只能被1和它本身整除(即只有1和它本身两个正约数)，这个自然数就叫做质数(或素数)。 (2) 合数；一个大于1的自然数，除了能被1和它本身整除外，还能被其它的正整数整除，这个自然数就叫做合数 (3) 自然数1，即不是质数，也不是合数。 2. 质数的判定：）查表法；)试除法,试除法依据,定理123 如果a是合数，p是a的最小约数，那么 p,推论 如果一个大于1的数a不能被不大于 的任一质数整除，那么a是质数,例：判断667与991是质数还是合数,解 由于 ，因此用225之间的质数去试除，试除结果有23667，所以667是合数 由于 ，因此用231之间的质数去试除，由试除结果可知231之间的质数都不能整除991，所以991是质数；,3. 相关定理 1）一个质数如果不能整除一个自然数，那么它就和这个自然数互质。 2）大于1的自然数，至少有一个约数是质数。 3）质数的个数无限。 ）算术基本定理：把一个合数分解质因数，如果不考虑质因数的次序，分解的结果是唯一的 ）质数与互质数是两个不同的概念,整数N的标准分解式,根据算术基本定理，如果把一个整数N的质因数分解式中的质因数按照从小到大的顺序排列，并且相同的质数连乘都用幂的形式表示，那么整数N的质因数分解的结果可以写成下面形式 这里p1p2p3pn，且p1，p2，p3，pn都是质数，1, 2, , n是自然数，其中i表示质数pi在N中出现的重数通常把上面分解式叫做整数N的标准分解式,定理1.4.3 和 推论,我喜欢数学,定理1.4.3 设 ，则 d 是 a 的正约数的充要条件是,自然数的所有正约数的个数及所有正约数的和与积,我喜欢数学,定义 1.7 ( a )表示正整数 a 的所有正约数的个数 (也称除数函数 ) 如 ( 2 ) = 2 , ( 4 ) = 3 ，等等 ( a )表示正整数 a 的所有正约数的和，如 (2) = 3, ( 4 ) = 7，等等。 1( a)表示正整数 a 的所有正约数的乘积如1( 4 ) = 8 , 1( 10 ) = 100，等等,定理1. 26 如果自然数a的标准分解式为 那么 (1)(a) (1 +1)(2 +1)(n +1) = (i+1) (2)(a) (1+ p1+ p12+ p1 1 ) (1+ p2+ p22+ + p22) (1+ pn+ pn2+ pn n ),(3)1(a) ,例1、 已知两个数的最大公约数为8，最小公倍数为128，求这两个数,解 设这两个数为a，b,则由定理110的推论2可知存在整数，使a8t1，b=8t2，且(t1，t2)=1 因为ab(a，b)X a，b，所以得 64 t1t2 =8 X128， t1t216 由于(t1,t2)1，所以 t1=1，t216或t1=16，t21 因此所求的两数为 a=8，b128(或a128，b=8),例2、用分解质因数法求数1200与1134的最大公约数最小公倍数,解 因为1200=24352，1134=2347 所以 (1200，1134)2 36 1200，1134 24 3452 7226800 说明 通过分解质因数求几个数最大公约数与最小公倍数的方法是这样的: 先将所给的各个数分别进行质因数分解把每个公有的质因数，取指数最小的幂相乘，所得的结果就是这几个数的最大公约数，如果把各个公有的质因数的最高次幂以及各个数独有的质因数的幂相乘，所得的结果就是这几个数的最小公倍数,例3、 设a1，a2，a11是整数，b1, b2, ， ,b11是它们的一个排列，求证乘积(a1-b1)