质因数分解及个数定理的正反应用资料

《质因数分解及个数定理的正反应用资料》由会员分享，可在线阅读，更多相关《质因数分解及个数定理的正反应用资料（10页珍藏版）》请在金锄头文库上搜索。

1、质因数个数定理的正反应用 ? 质因数个数定理的正反应用 一、知识点：一、知识点： 1、约数（、约数（又称又称因数因数）和倍数）和倍数 1）、如果数 a能被数 b 整除, a就叫 b 的倍数, b 就叫 a的约数（因数），如 10=2x5，则 2 和 5 都是 10 的因数，10 是 2 的倍数，也是 5 的倍数； 16=2x8=1x16=4x4，则 1、2、4、8、16 都是 16 的因数（约数），反过来 16 是 1、2、4、8、16 的倍数 2）、一个数的约数（因数）的个数是有限的,其中最小的约数是 1,最大的约数 是它本身. 3）、一个数的倍数的个数是无限的,其中最小的是它本身,它没有最

2、大的倍数. 注意：因数总是成对出现，在枚举因数的时候一定要成对枚举，不要有遗漏；注意：因数总是成对出现，在枚举因数的时候一定要成对枚举，不要有遗漏； 2、如果一个数、如果一个数 c 既是数既是数 a 的因数，又是数的因数，又是数 b 的因数，那么的因数，那么 c 叫做叫做 a 与与 b 的公因数。 如两个数的公因数有多个，其中中最大的一个，叫做这两个数的最大公因数。 用（ 的公因数。 如两个数的公因数有多个，其中中最大的一个，叫做这两个数的最大公因数。 用（ a，b）表示，例如：（）表示，例如：（1，2）=1 最大公因数的性质：最大公因数的性质：两个数的任意公因数，都是最大公因数的因数，也是这

3、两个数 和、差、积的因数； 举例：12 和 30 的最大公因数：（12,30）=6； 比如：16=1x16=2x8=4x4； 24=1x24=2x12=3x8=4x6； 那么 1、2、4、8 既是 16 的约数也是 24 的约数，其中 8 是 16、24 的最大公约数（公 因数），（16，24）=8 16=1x16=2x8=4x4； 24=1x24=2x12=3x8=4x6； 56=1x56=2x28=4x14=7x8 则 1、2、4、8 既是 16 的约数也是 24、56 的约数，其中 8 是 16、24、56 的最大公约 数（公因数），（16，24，56）=8 3、两个或多个整数公有的倍数

4、叫做它们的公倍数。 两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数 、两个或多个整数公有的倍数叫做它们的公倍数。 两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数 a，b 的最小 公倍数记为 的最小 公倍数记为a，b，同样的，同样的，a，b，c 的最小公倍数记为的最小公倍数记为a，b，c，多个整数的最小公 倍数也有同样的记号。 最小公倍数的性质： ，多个整数的最小公 倍数也有同样的记号。 最小公倍数的性质：两个数的任意公倍数，都是最小公倍数的倍数； 注意：注意：0 要除外，要除外，0 不能为最小公倍数不能为最小公倍数 例如：2x1=2，2x2=4，2x3=6，2x

5、4=8，2x5=10，2x10=20 5x1=5，5x2=10，5x3=15，5x4=20 10、20 都是 2 的倍数，也是 5 的倍数，因此 10、20 称为 2、5 的公倍数，其中 10 最小，因此 10 是 2 和 5 的最小公倍数，记为2，5=10 4、如果一个数、如果一个数 a 只有只有 1 和和 a 两个因数；另外一个数两个因数；另外一个数 b 只有只有 1 和和 b 两个因数，则两个因数，则 a、b 为互质数，如：为互质数，如：5 和和 13， 5=1x5；13=1x13，则，则 5 和和 13 为互质数为互质数 5、特殊情况下几个数的最大公约数和最小公倍数、特殊情况下几个数的

6、最大公约数和最小公倍数. （1）如果几个数中）如果几个数中,较大数是较小数的倍数较大数是较小数的倍数,较小数是较大数的约数较小数是较大数的约数,则较大数是它们的 最小公倍数 则较大数是它们的 最小公倍数,较小数是它们的最大公约数较小数是它们的最大公约数. 若 A 是 B 的倍数，则(A,B)=B，A,B=A； （2）如果几个数两两互质）如果几个数两两互质,则它们的最大公约数是则它们的最大公约数是 1,最小公倍数是这几个数连乘的积最小公倍数是这几个数连乘的积. 若 A、B 互质，则(A,B)=1，A,B =Ax B； 6、质数和合数、质数和合数 1）、一个数只有 1 和它本身两个约数,这个数叫做

7、质数（素数），例如 5=1x5. 2）、一个数除了 1 和它本身外,还有别的约数,这个数叫做合数，例如 10=1x10=2x5 3）、1 既不是质数,也不是合数. 4）、自然数按约数的个数可分为：质数、合数 质因数个数定理的正反应用 ? 5）、自然数按能否被 2 整除分为：奇数、偶数 7、互质的概念：、互质的概念： 1）、互质：如果两个数最大公因数为 1，则称这两个数互质； 2）、两数互质的几种常见情况：连续自然数；连续奇数；两个质数 举例：5 和 7 互质；10 和 9 互质； 8、最大公约数求法 枚举法 、最大公约数求法 枚举法 枚举法：将两个数的因数分别一一列出，从中找出其公因数，再从公

8、因数中找出最大 的一个，即为这两个数的最大公因数。 例：求 30 与 24 的最大公因数。 30 的正因数有：1,2,3,5,6,10,15,30。 24 的正因数有：1,2,3,4,6,8,12,24。 易得其公因数中最大的一个是 6，所以 30 和 24 的最大公因数是 6。 短除法短除法 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数 A、B， 再画一个短除号，接着在原本写除数的位置写两个数公有的质因数 Z（通常从最小的质 数开始），然后在短除号的下方写出这两个数被 Z 整除的商 a，b，对 a，b 重复以上步 骤，以此类推，直到最后的商互质为止，再把所有的除数相乘

9、，其积即为 A，B 的最大 公因数。 （短除法同样适用于求最小公倍数，只需将其所有除数与最后所得的商相乘即可） 例：求 12 和 18 的最大公约数。 解：用短除法，由上图，易得 12 和 18 的最大公约数为 23=6。 分解质因数分解质因数 将需要求最大公因数的两个数 A，B 分别分解质因数，再从中找出 A、B 公有的质因 数，把这些公有的质因数相乘，即得 A、B 的最大公约数。 例：求 48 和 36 的最大公因数。 把 48 和 36 分别分解质因数： 48=22223 36=2233 其中 48 和 36 公有的质因数有 2、2、3，所以 48 和 36 的最大公因数是 223=12

10、。 辗转相除法辗转相除法 （欧几里得算法）对要求最大公因数的两个数 a、b，设 ba，先用 b 除 a，得 a b=qr1 (0r1b)。若 r1=0，则（a，b）=b；若 r10，则再用 r1 除 b，得 b r1=qr2 (0r2r1），若 r2=0，则（a，b)=r1，若 r20，则继续用 r2 除 r1如此 循环，直到能整除为止。其最后一个非零余数即为（a，b）。 例：求 8251 和 6105 的最大公因数。 考虑用较大数除以较小数，求得商和余数： 82516105=12146 61052146=21813 21461813=1333 1813333=5148 质因数个数定理的正反应

11、用 ? 333148=237 14837=4 最后除数 37 是 148 和 37 的最大公因数，也就是 8251 与 6105 的最大公因数。 更相减损术更相减损术 更相减损术出自九章算术的一种求最大公约数的算法，它原本是为约分而设计 的，但它适用于任何需要求最大公约数的场合。其原文为：“可半者半之，不可半 者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言就是 第一步：任意给定两个正整数 a、b；判断它们是否都是偶数。若是，则用 2 约简；若 不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小 数。继续这个操作，直到

12、所得的减数和差相等为止。这个数就是 a、b 的最大公约数。 例：求 98 与 63 的最大公因数。 分析：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减： 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98 和 63 的最大公约数为 7。 注：以上首三个方法同样适用于求多个自然数的最大公约数 约数（因数）个数定理 注：以上首三个方法同样适用于求多个自然数的最大公约数 约数（因数）个数定理 对于一个大于 1 正整数 n 可以分解质因数：n=(p1)(a1)x (p2)(a2)x (p3)(a3)x x (pk)(ak)

13、。 则 n的正约数的个数就是(a1+1)(a2+1)(a3+1)(ak+1) 其中 a1、a2、a3ak是 p1、p2、p3， pk 的指数。 定理简证定理简证 首先同上，n 可以分解质因数：n=p1a1p2a2p3a3xxpkak, 由约数定义可知 p1a1 的约数有:p10, p11, p12p1a1 ，共（a1+1）个;同理 p2a2 的约数有（a2+1）个pkak 的约数有（ak+1）个。 故根据乘法原理：n 的约数的个数就是(a1+1)(a2+1)(a3+1)(ak+1)。 例题：正整数 378000 共有多少个正约数？ 解：将 378000 分解质因数 378000=2433537

14、1 由约数个数定理可知 378000 共有正约数(4+1)(3+1)(3+1)(1+1)=160 个。 9、最小公倍数计算方法 （ 、最小公倍数计算方法 （1）分解质因数法 先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几 个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如求 ）分解质因数法 先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几 个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如求 45 和和 30 的最小公倍数。的最小公倍数。 45=3*3*5 30=2*3*5 不同的质因数是

15、 不同的质因数是 2,5,3 是他们两者都有的质因数，由于是他们两者都有的质因数，由于 45 有两个有两个 3，30 只有一个只有一个 3，所以计算最小公倍数的时候乘两个，所以计算最小公倍数的时候乘两个 3. 最小公倍数等于 最小公倍数等于 2*3*3*5=90 又如计算又如计算 36 和和 270 的最小公倍数的最小公倍数 36=2*2*3*3 质因数个数定理的正反应用 ? 270=2*3*3*3*5 不同的质因数是 不同的质因数是 5。2 这个质因数在这个质因数在 36 中比较多，为两个，所以乘两次；中比较多，为两个，所以乘两次；3 这个 质因数在 这个 质因数在 270 个比较多，为三个

16、，所以乘三次。 最小公倍数等于 个比较多，为三个，所以乘三次。 最小公倍数等于 2*2*3*3*3*5=540 20 和和 40 的最小公倍数是的最小公倍数是 40 （2）公式法 由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（ ）公式法 由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）a， b=ab。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上 述公式求出它们的最小公倍数。 例如，求 。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上 述公式求出它们的最小公倍数。 例如，求18，20，即得，即得18，20=1820（18，20）=18202=180。求几个 自然数的最小公倍数，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与 第三个数的最小公倍数，