初等数论单元复习

1、单元小结第一章第一章 整数的整除性整数的整除性 定义定义1.11.1 设设 a，b Z ，b00，如果存在，如果存在 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 的的倍

2、数倍数，b就叫做就叫做a的的约数约数.l2、当然约数与真约数、当然约数与真约数:一般地，在整数一般地，在整数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的真约数，则的真

3、约数，则1 a b 4、整除的基本性质、整除的基本性质:4 4、带余除法、带余除法 设设a, b是两个整数，是两个整数，b 0，则一定，则一定有并且只有并且只有有两个整数两个整数 q , r 使得使得 a= bq + r,0rb，如果如果 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除

4、以除以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互质的必要且充

5、分条件是存互质的必要且充分条件是存在整数在整数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

6、, ,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.8与定理与定理1.3.9 可类比定理可类比定理1.3.6与定理与定理1.3.7 得到

7、。得到。 定理定理1. 3. 6 (a1，a2，ak) = d的充要条件是的充要条件是12,1kaaaddd多个数的最大公约数和最小公倍数多个数的最大公约数和最小公倍数定理定理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).我喜欢数学我喜欢数学互质的性质互质的性

8、质定理定理1.3.15 若若a | c, b | c, (a, b)=1, 则则 ab | c. 1.3质数与合数质数与合数 算术基本定理算术基本定理 1. (1) 质数质数(素数素数)：一个大于一个大于1的自然数，如果只的自然数，如果只能被能被1和它本身整除和它本身整除(即只有即只有1和它本身两个正约和它本身两个正约数数)，这个自然数就叫做质数，这个自然数就叫做质数(或素数或素数)。 (2) 合数；合数；一个大于一个大于1的自然数，除了能被的自然数，除了能被1和它和它本身整除外，还能被其它的正整数整除，这个自本身整除外，还能被其它的正整数整除，这个自然数就叫做合数然数就叫做合数 (3) 自然

9、数自然数1，即不是质数，也不是合数。，即不是质数，也不是合数。 2. 质数的判定：质数的判定：）查表法；）查表法；)试除法试除法试除法依据试除法依据 定理123 如果如果a是合数，是合数，p是是a的最的最小约数，那么小约数，那么 p a 推论推论 如果一个大于如果一个大于1的数的数a不能被不大于不能被不大于 的任一质数整除，那么的任一质数整除，那么a是质数是质数 a 例：判断667与991是质数还是合数 解 由于，因此用225之间的质数去试除，试除结果有23667，所以667是合数 由于，因此用231之间的质数去试除，由试除结果可知231之间的质数都不能整除991，所以991是质数； 6672

10、5.82648.31991 3. 相关定理相关定理 1）一个质数如果不能整除一个自然数，那么）一个质数如果不能整除一个自然数，那么它就和这个自然数互质。它就和这个自然数互质。 2）大于）大于1的自然数，至少有一个约数是质数。的自然数，至少有一个约数是质数。 3）质数的个数无限。）质数的个数无限。 ）算术基本定理：把一个合数分解质因数，）算术基本定理：把一个合数分解质因数，如果不考虑质因数的次序，分解的结果是唯一如果不考虑质因数的次序，分解的结果是唯一的的 ）质数与互质数是两个不同的概念）质数与互质数是两个不同的概念整数N的标准分解式 根据算术基本定理，如果把一个整数根据算术基本定理，如果把一个

11、整数N的质因数的质因数分解式中的质因数按照分解式中的质因数按照从小到大从小到大的顺序排列，并的顺序排列，并且且相同的质数连乘都用幂的形式表示相同的质数连乘都用幂的形式表示，那么整数，那么整数N的质因数分解的结果可以写成下面形式的质因数分解的结果可以写成下面形式 这里这里p1p2p3pn，且，且p1，p2，p3，pn都都是质数，是质数，1, 2, , n是自然数，其中是自然数，其中i表示质数表示质数pi在在N中出现的重数通常把上面分解式叫做中出现的重数通常把上面分解式叫做整数整数N的标准分解式的标准分解式,2121nnpppN定理定理1.4.3 1.4.3 和和 推论推论我喜欢数学我喜欢数学定理

12、定理1.4.31.4.3 设 ，则 d 是 a 的正约数的充要条件是1iniiap我喜欢数学我喜欢数学定义定义 1.71.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的

13、标准分解式为那么 (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 )1212,nnappp(3)1(a) aa 例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 因此所求的

14、两数为 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是整