第一讲数字问题(数论复赛辅导)

1、包头市数学联赛辅导 复赛数论初步选讲-北重三中 樊增平第一讲 数字问题【基础知识】一质数与合数及其性质1正整数分为三类： 单位数1； 质数（或素数）：一个大于1的正整数，如果它的因数只有1和它本身，则称为质数（或素数）；合数：如果一个正整数包含有大于1且小于其本身的因子，则称这个正整数为合数.二.最大公约数及性质1、定义（最大公约数） 设不全为零，同时整除的整数（如）称为它们的公约数(也称公因数)。因为不全为零，故只有有限多个公因数，我们将其中最大一个称为的最大公约数，用符号（）表示。显然，最大公约数是一个正整数。当（）1（即的公约数只有）时，我们称与互素（也称互质）。 同样，如果对于多个（不

2、全为零）的整数，可类似地定义它们的最大公约数（）。若（）1，则称互素。请注意，此时不能推出两两互素；但反过来，若两两互素，则显然有（）1。2有关质（素）数的一些性质(1) 互质，若，则；（2）若是质（素）数，为任一整数，则必有或（）1；（3）设为个整数，为质（素）数，且，则必整除某个（ ），特别地，若是质数，且，则；（4）（算术基本定理，也叫整数的唯一分解定理）任何一个大于1的正整数，能唯一地表示成质（素）因数的乘积（不计较因数的排列顺序）；（5）任何大于1的整数能唯一地写成的形式，其中为质（素）数（）。上式叫做整数的标准分解式；（6）若的标准分解式为，的正因数的个数记为，则。若整数的标准分解

3、式是式，则是的正因数的充要条件是：说明：式不能称为整数的标准分解式，由于其中的某些可能取零值（如果不含某个素因数，则）.3、最大公约数的性质例如任意改变的符号，不改变（）的值，即；（）可以交换，（）（）；（）作为的函数，以为周期，即对于任意的实数，有（）（）等等。为了更详细地介绍最大公约数，我们给出一些常用的一些性质：（1）设是不全为0的整数，则存在整数，使得；（2）（裴蜀定理）两个整数互素的充要条件是存在整数，使得；事实上，条件的必要性是性质（1）的一个特例。反过来，若有使等式成立，不妨设，则，故及，于是，即，从而。（3）若，则，即的任何一个公约数都是它们的最大公约数的约数；（4）若，则；（

4、5）若，则，因此两个不互素的整数，可以自然地产生一对互素的整数；（6）若，则，也就是说，与一个固定整数互素的整数集关于乘法封闭。并由此可以推出：若，对于有，进而有对有。（7）设，若，则；（8）设正整数之积是一个正整数的次方幂（），若（）1，则都是整数的次方幂。一般地，设正整数之积是一个正整数的次方幂（），若两两互素，则都是正整数的次方幂。特别地，若，且，是整数的平方，则也是整数的平方。（9）辗转相除法：设两数为a、b(ba)，求它们最大公约数(a、b)的步骤如下： 用b除a，得，若，则(a，b)b； 若，则再用除b，得，若，则(a，b). 若，则继续用除，如此下去，直到能整除为止，其中最后一个

5、非零余数即为(a，b).例如：求212与36的最大公因数.三.最小公倍数及性质1、最小公倍数定义： 设是两个非零整数，一个同时为倍数的数称为它们的公倍数，的公倍数有无穷多个，这其中最小的一个称为的最小公倍数，记作，对于多个非零实数，可类似地定义它们的最小公倍数。2、最小公倍数的性质（1）与的任一公倍数都是的倍数，对于多于两个数的情形，类似结论也成立；（2）两个整数的最大公约数与最小公倍数满足：（但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立）；（3）若两两互素，则；（4）若，且两两互素，则。【例题分析】1证明：被1001整除。证明：所以整除。2对正整数，记为的十进制表

6、示中数码之和。证明：的充要条件是。证明：设（这里，且），则，于是有对于，知，故式右端个加项中的每一个都是9的倍数，从而由整除的性质可知它们的和也能被9整除，即。由此可易推出结论的两个方面。3设正整数的最大公约数是1，并且，证明是一个完全平方数。证明：设，则，其中，由于，故，现在问题中的等式可以转化为由此可见整除。因为，故，同样可得，再由便可以推出。设，其中是一个正整数。一方面，显然整除；另一方面，结合式，得，故，从而，但，故。因此，故，这样就证明了是一个完全平方数。4求出所有的正整数对，使得与都是整数.解：由于是对称的，不妨设.当时，则，从而2；当时，若时，则有，所以或3；若时，由于是一个整数

7、，从而使得即，所以。又由于，所以。所以，从而得或3， ；综上知所有的为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).5数列的通项公式为，记，求所有的正整数，使得能被8整除 解：记注意到，可得因此，Sn+2除以8的余数，完全由Sn+1、Sn除以8的余数确定.，故由(*)式可以算出各项除以8的余数依次是1,3，0,5，7,0，1,3，它是一个以6为周期的数列，从而，故当且仅当.6设是正整数，且，它们的最小公倍数是最大公约数的120倍，求。解：设，则，其中且，于是。所以即由及（2）可得：。由（1）可知只能取从而或29，故或。7设，则。证明

8、：设，则，其中。于是，已知条件转化为，故更有，从而转化为，但是，故，结合，知必有，同理 ，因此。8 都是正整数，是否存在整数使得对任意的正整数，与互质？解：令，则，于是存在整数使得，令，则对任意的正整数，设，有即，而，所以，即对任意的正整数，（，）1。9设正整数满足，证明：不是质（素）数。证法一：由，可设其中。由意味着有理数的分子、分母约去了某个正整数后得既约分数，因此，同理，存在正整数使得因此，是两个大于1的整数之积，从而不是素数。注：若正整数适合，则可分解为及的形式，这一结果在某些问题的解决中很有作用。证法二：由，得，因此，因为是整数，故也是整数。若它是一个素数，设为，则由可见整除，从而素

9、数整除或。不妨设，则，结合推出，而这是不可能的（因为）。10若是正奇数，证明：.证明：由于为奇数，故，又，从而（，）（），而（）1，故。11 已知，证明：对于任意大于1的正整数，都有两两互素.证明：设（其中出现次）。由，故对于有，则是含有0次项的多项式。因此，除以的余数为1。假设存在整数可整除和，由于，则除以的余数为1，即1，进而，矛盾！从而可知两两互素。12证明：如果和都是大于3的素数，则6是的因子。证明：因为是奇数，所以2是的因子。又因为，除以3的余数各不相同，而与都不能被3整数。于是6是的因子。13设是正整数，若不是整数，则必为无理数。证明：若是非整数的有理数，则可设，于是，。因为，故可知。但，这与矛盾！证毕。14已知，且，试问的充要条件是吗？解：因为，所以；又，所以；令，则有又因为，所以从而上式且为奇数，即的充要条件是且为奇数。15我们知道有1个质因子，且；有2个质因子，且如此下去，我们可以猜想： 至少有个质因子，且，试证明之.证明：令，则.根据整数唯一分解定