数学奥赛辅导 第二讲 整 除.docVIP

数学奥赛辅导 第二讲 整除 知识、方法、技能 整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题. Ⅰ. 整数的整除性 初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如是整除，，则不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除性. 定义一：（带余除法）对于任一整数和任一整数，必有惟一的一对整数，使得，，并且整数和由上述条件惟一确定，则称为除的不完全商，称为除的余数. 若，则称整除，或被整除，或称的倍数，或称的约数（又叫因子），记为.否则，| . 任何的非的约数，叫做的真约数. 0是任何整数的倍数，1是任何整数的约数. 任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若 （2）若 （3）若，则反之，亦成立. （4）若.因此，若. （5）、互质，若 （6）为质数，若则必能整除中的某一个. 特别地，若为质数， （7）如在等式中除开某一项外，其余各项都是的倍数，则这一项也是的倍数. （8）n个连续整数中有且只有一个是n的倍数. （9）任何n个连续整数之积一定是n的倍数. 本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了. 定理一：设大于1的整数的标准分解式为为质数，均为非负整数），则a的约数的个数为 . 所有的约数和为： . 事实上，由算术基本定理的推论知，而各约数的和就是展开后的各项之和，所以 例如，25200=24·32·52·7，所以 ， . Ⅱ. 最大公约数和最小公倍数 定义二：设、是两个不全为0的整数.若整数c满足：，则称的公约数，的所有公约数中的最大者称为的最大公约数，记为.如果=1，则称互质或互素. 定义三：如果、的倍数，则称、的公倍数. 的公倍数中最小的正数称为的最小公倍数，记为. 最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用表示的最大公约数，表示的最小公倍数. 若，则称互质，若中任何两个都互质，则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立. 因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0.同时，由于有相同的公约数，且（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数. 显然，若的标准分解式为为质数，为非负整数），则 ① ② 例如 3960=23·32·5·11， 756=22·33·7， 则 （3960，756）=22·32=36， [3960，756]=23·33·5·7·11=83160. 求最大公约数也可以用辗转相除法，其理论依据是： 定理二：设a、b、c是三个不全为0的整数，且有整数t使得，则a、b与b、c有相同的公约数，因而，即 因为，若、b的任一公约数，则由、c的公约数；反之，若、c的任一公约数，、b的公约数. 辗转相除法：设、， 由带余除法有 ③ 因为每进行一次带余除法，余数至少减1，即，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得，而，故由定理二得： 例如，（3960，756）=（756，180）=（180，36）=36. 具体算式如下： 5（q1） 3960（a） 756（b） 4（q2） 3780 720 180（r1） 36（r2） 5（q3） 180 0（r3） 由定义和上述求法不难得出最大公约数和最小公倍数的如下性质： （1）. （2）设的公约数，则特别地，若. （3）设是任意n个正整数，如果， 则. 因，如此类推得出能整除是它们的一个公约数.又设的任一公约数，则，因而，同理可推出，如此类推最后可得. 于是，故是最大公约数. （4）若，则一定有整数，使得. 特别地，存在. 这可由辗转相除法的③式逆推而得. （5）若. （6） ①； ②的任一公倍数，则； ③，特别地，若. ①可由③直接得到，②可由最小公倍数定义得，③根据①、②式知， . （7）设是任意个正整数.若mn，则. 这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方法来证明.