《提优教程》教案第35讲整数性质

1、第16讲整数的性质初等数论的基本研究对象是整数两个整数的和、差、积都是整数，但商却不一定是整 数由此引出了数论中最基本的概念：整除.整除性理论是初等数论中最基础的部分，它是在带余除法的基础上建立起来的.整数a除以整数 b （b丰0），可以将a表示为a=bq + r,这里q , r是整数，且 Ow rv b. q 称为a除以b所得的商，r称为a除以b所得的余数.当r=0时，a=bq，称a能被b整除，或称b整除a,记为b | a, b叫做a的因数，a叫 做b的倍数；q取1，则a = b, a也是它本身的因数.当U 0时，称a不能被b整除，b不整除a，记作b卜a .若c | a, c | b，则称c

2、是a, b的公因数，a, b的最大公因数d记为（a, b）. 若a | c, b | c,则称c是a, b的公倍数，a, b的最小公倍数 M记为a, b.一个正整数，按它的正因数个数可以分为三类.只有一个正因数的正整数是1 ;有两个正因数的正整数称为素数（质数），素数的正因数只有1和它本身；正因数个数超过两个的正整数 称为合数，合数除了 1和它本身外还有其他正因数.任何一个大于1的整数均可分解为素数的乘积，若不考虑素数相乘的前后顺序，则分解 式是惟一的.一个整数分解成素数的乘积时，其中有些素数可能重复出现，把分解式中相同 的素数的积写成幕的形式，大于1的整数a可以表示为：a= Pi1 P22

3、PiPsS，其中 i=l, 2,，s.以上式子称为a的标准分解式.大于I的整数的标准分解式是惟一的（不考虑乘积的先后顺序）.若a的标准分解式是a= P11 P22口PsS，其中i=l, 2，s，则d是a的正因数的充要条件是 d= 1 P22Pii - PsS，其中0 w B w ai, i=l , 2，S .由此可知，a的正因数的个数为 d（a）=（ a1+1） （ a+1）（as+1）.由a的标准分解式 a= P11 P22PipsS （i=l, 2，s）,若a是整数的k次方，则a（i=l, 2，s）是k的倍数.若a是整数的平方，则 ai（i=l, 2，s）是偶数.推论：设a=bc，且（b,

4、 c）=1，若a是整数的k次方，则b, c也是整数的k次方.若a 是整数的平方，则 b, c也是整数的平方.A类例题例1 .若任何三个连续自然数的立方和都能被正整数a整除，则这样的a的最大值是（）A. 9B. 3C. 2D. 1分析 观察最小的三个连续自然数的立方和 36 , a是它的约数，a不会超过36，不能排除任 何选择支；观察第二个小的三个连续自然数的立方和，进一步缩小a的范围，可以排除取偶数的可能。当前面几个都是某数的倍数时，可以猜想出a的最大值，但最好能证明所有“三 个连续自然数的立方和”都是某数的倍数。解 记 an = n3+ (n + 1)3+ (n + 2)3，贝U ai= 1

5、3+ 23 + 33 = 36 = 4 X 9,a2= 23+ 33 + 43= 99 为奇数，则 a|ai, a|a2, (ai, a2)=9，故 a| 9，所以 a = 1, 3 , 9。又 an = n3+ (n + 1)3 + (n + 2)3 = 3n3 + 9n2+ 15n + 9 = 3n3+9n2+ 6n + 9n + 9 = 3n(n2 + 3n + 2) + 9(n + 1) = 3n(n + 1)( n + 2) + 9(n + 1),-9 | an，故 a max = 9，选 A。说明 解法中，把3n3+ 9n2 + 15n + 9分为3n(n2+ 3n + 2)与9(

6、n + 1)两部分，分别说明其为9的倍数。在考虑整除的证明时，把整数 n的多项式分成几组分别因式分解是常用的方法。例2 若p是大于3的质数，则p2除以24的余数为1。分析：即证明p2 1是24的倍数，也即证明 p2 1既是3的倍数又是8的倍数。p 1、p+1之间只有一个质数 p，而连续的两个自然数中必有2的倍数，连续的三个自然数中必有3的倍数。证明1 v p是大于3的质数， p不是偶数，不是3的倍数，又 p2仁(p 1)(p+1)，连续的三个整数中必有3的倍数， p 1、p+1中必有3的倍数，且p 1、p+1是连续的两个偶数，(p 1)(p + 1)是8的倍 数。 p2 1= (p 1)(p

7、+ 1)是24的倍数，即p2除以24的余数为1。证明2设p=6 n (6n ,6n 2,6 n+3均为合数)，则(6n )2=36 n2 2n+1=12 n(3n 1)+1 ,v n和3n 必为一奇一偶， n(3n 1)为偶数。 12n(3n )必为 24 的倍数， (6n 1)2=24k+1即p2除以24的余数为1。说明 大于3的质数，必定是奇数，又不是3的倍数，所以一定是形如6n1的数。6是24的约数，用这样的形式表出后再变形，容易推出结论。例3 试证明21p+4是既约分数。14p+3分析 即证明(21 p+4 , 14p+3)=1。若a、b、c是三个不全为0的整数，且有整数t使得a=bt

8、+c,贝U a、b 与 b、c 有相同的公约数，因而 (a, b)= ( b, c)，即(a, b) = ( a bt, b)。可 以用此法化简。证明 v (21 p+4 , 14p+3)= (21 p+4 14p 3, 14 p+3)=(7p+1 , 14p+3)= (7 p+1 , 14p+3 14 p2)=(7p+1 , 1)=1 ,21 p+414 p+3是既约分数。说明证明过程中用到性质(a, b)= (a - bt, b)，因为，若d是a、b的任一公约数，则由d|a, d|b和a bt c知d |c,即d是b、c的公约数；反之，若 d是b、c的任一公约数，d 也是a、b的公约数，所

9、以a，b与a bt，b有相同的最大公约数。求两个正整数的最大公约 数常用辗转相除法。链接辗转相除法：设a、b N*,且a b，由带余除法有abq1r1,0r1b,b伦 D,0r2r1LLrn2rn 心 rn,0rnrn1 临 1 rn1,rn1 0-因为每进行一次带余除法，余数至少减1，即b n2 rn rn+1，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得rn丰0 ,而rn+1 = 0 ,故得：rn= (rn+1, rn)= (rn, rn-1)=(2, D)= (r1, b)= (a, b)例如，(3960 , 756 ) = ( 756 , 180 ) = (180 ,

10、36) =36。例4. 一个自然数，它的末位数字移到首位时，数值便为原来的5倍，求满足条件的最小自然数。分析正整数有多种表示形式，选择适当的形式有利于问题解决。由题目的条件，此表示形式应该把数的末位数字反映出来，而其他位置上的数字可以整体的看待。解 设所求数为a 1 a2 an-1 an,由已知得a*a1a2an-1=5a1a2an-1 an,-an x 10 n 1+a 1 a2 an-1 =5(10 x a1 a2an-1 +an), (10n-1 5)an=49aia2an-i, anX 99L395 =49aia2an-i，(n 2)个 an是个位数字，不能被 49整除，9995至少能

11、被7整除，它最小时应为 99995，此时n=6 ,若有解，则式为 a6X 99995=49 aia2a3a4a5,- a6X i4285=7 aia2a3a4a5, i4285 不能被 7 整除， a6=7, aia2a3a4a5=i4285 ,满足条件的最小自然数为i42857 。说明 9995能被7整除是必要条件，99995是满足被7整除条件的最小数，但99995是不是问题的解还要进一步探讨，如果寻找到满足条件的 a6和aia2a3a4a5,则aia2a3a4a5a6就则要考虑比99995略大的形如99是问题的解；如果找不到满足条件的a6和ai a2a3a4a5,95的数。情景再现i .一

12、个六位数，如果它的前三位数字与后三位数字完全相同，顺序也相同，则它可以不B . 9的倍数C. ii的倍数2 .若p与d都是正整数，其中D. i3的倍数d不能被6整除，当p、p + d、p+2d都是质数时，则 p +3d心曰疋疋A.质数B. 9的倍数C. 3的倍数D.质数或是9的倍数3.已知n为正整数，若片n 6n3n 是一个既约分数，那么这个分数的值等于.i6求具有下列性质的最小正整数(i)它以数字6结尾;如果把数字6移到第一位之前,所得的数是原数的4倍。B类例题例 5 .试证 1999|(1998 1998+2000 2000 2001).分析：1998 1998和2000 2000是很大的

13、数字，它们除以1999的余数常常借助于二项式定理或xn+yn, xn yn的因式分解公式。证明:由二项式定理(a + b)n= Cn an+ Cn an-1b + + Cn an-kbk + + Cn bn,知(a+b)n=aM + bn，由此可得1998 1998=(1999 1) 1998=1999 M+1 ,2000 2000-=(1999+1) 2000-=1999 N+1 , 这里M , N Z.于是1998 1998+2000 2000 2001=1999 M + 1999 N 1999=1999( M + N 1),从而 1999 | (1998 1998 +2000 2000

14、2001).说明对于整数的高次方幕的整除，除了运用同余的性质，二项式定理和因式分解的裴 蜀定理是常用的工具。链接因式分解公式(裴蜀定理)对大于1的整数n有xn yn =(x y)(xn-1 +xn-2y+xn-3y2+xyn-2+yn-1);对大于1的奇数n有xn+yn =(x+y)(xn-1 xn-2y+xn-3y2 xyn-2+yn-1)；对大于1的偶数n有xn yn =(x+y)(xn-1 xn-2y+xn-3y2 +xyn-2 yn-1)；二项式定理：(a+b)n=Cn0an+C：an-1b+ + Cnkan-kbk + + C；bn;其中Cn =是整数。n(n 1)(n 2)(n k

15、+1)k(k 1)3 x 2 x 1若 a, b 是整数，则(a+b)n=aM +bno例6.已知自然数a、b、c满足a , b=24 , (b, c)=6 , c, a=36，则满足上述条件的数组(a , b, c)有多少组?分析 条件a , b=24及c, a=36意味着a、b、c不大，都是24或36的约数，对于a,它既是24又是36的约数，所以它是12的约数。而b，满足(b, c)=6，则是6的倍数，是24 的约数，只能取6 ,12 , 24。注意到a的取值，b更是只能取24。解 a | 24， a | 36a|12a=1， 2， 3， 4， 6， 126 | b, b | 24b=6,

16、 12, 246 | c, c | 36c=6, 12, 18, 36若 a=1 , 2, 3, 4 , 6, 12 时，由a , b=24，得 b=24 ,a 不是 9 的倍数 由 a c=36 则 c 是 9 的倍数再由(b , c)=6，得 c=36 或 18( a=4 , 12 时),但(2436)=12 矛盾故 c=18 a=12 , b=24 , c=18 或 a=4 , b=24 , c=18 .即有 (12 24 18) (4 24 18)二组说明 例 6 的解法是数论中常用筛法 先粗选出可能的值 再从中筛出满足要求的数来。例7 .已知n是三位奇数，它的所有正因数(包括1和n)

17、的末位数字之和是 33,求满足条件的数 n 。分析：条件中隐含了整数的正因数个数是奇数。联想算术基本定理：n=pkqits ,正因数个数为d(n)=(k+1)(i+1)(s+1),题中每个因数均为奇数，因数的个数也是奇数，故 k , i , s 是偶数 所以 n 完全平方数。三位奇数是完全平方数 范围缩小到 11 个。还能把范围缩小点吗？解： 由题 所有因数是奇数 所有因数的个数是奇数所以 每个质因数的指数是偶数 n 是完全平方数；若是质数的平方数 则有 3 个因数 个位数字之和不能超过 27故为合数的完全平方数；这样的三位数只能在下列数中间： 152 212 252 272。逐个验算 得 n

18、=729 。说明 本例题的解法实质上还是筛选法 三位数有 900 个 三位奇数是其中一半 但如 果能从条件中发现是完全平方数 范围就非常有限了。例8 .已知m、n、k是正整数，且 mn | nm , nk | kn。证明：mk | km。( 2004年新西兰数 学奥林匹克)分析 条件mn | nm ,说明mn是nm的约数，对于给定的 m、n ,怎样去找到 mn与nm 的联系？必须具体一些。mn是nm的约数，则mn的每一个因数都是 nm的约数，考虑证明 设m、n、k中所有的质因数分别是P1, p2,ps ,不妨设p1 p20, i=l, 2，s.由 mn | nm 得 0 w n aW m由 n

19、k | kn 得 0w k 3i n0,证明：(22 +1) | ( 22 1)。6 .证明：当n为任何整数时，2n6 -n4 - n2能被36整除。7 . a是正整数，且a4 + a3 + a2 + a + 1是完全平方数，求所有满足条件的a。8 .设n为整数，则13除n2+5 n+23的余数的集合是。C类例题例9 .设p是质数，且p2 +71的不同正因数的个数不超过 10个，求p . (2006年江苏初 赛)分析 分解因数，可以先从 p的起始值开始探索.由例2, p2 1是24的倍数，p2+71 =p2 1+72 , 72也是24的倍数。所以23 , 31都是p2+71的因数。p2+71正

20、因数个数显然超过 8个。解 当p=2时，p2+71=75=5 2X 3，此时共有正因数(2+1) X (1 + 1)=6个，p=2满足条件；当p=3时，p2+7仁80=2 4X 5，此时共有正因数(4+1) X (1+1)=10个，p=3满足条件；当 p 3 时，p2+71 = p2 1+72=( p 1)( p + 1)+72，质数 p 必为 3k 1 型的奇数，p 1、P+1是相邻的两个偶数，且其中必有一个是3的倍数，所以(p 1)(p+1)是24的倍数，所以 p2+71是24的倍数.p2+7 仁24 X m , m 4 .若m有不同于2 , 3的质因数，那么p2+71的正因数个数(3 +

21、1) X (1+1) X (1 + 1) 10 ；若m中含有质因数3，那么p2+71的正因数个数(3 +1) X (2+1) 10;若m中仅含有质因数 2,那么p2+71的正因数个数(5 + 1) X (1 + 1) 10 ；所以p 3不满足条件；综上所述，所求的质数p是2或3 .说明 本题中，对于 p 3时的情况，也可以设p=6 n 1来讨论。注意数 n的正因数个数公式：若n的标准分解式是 n =pP22PsS，其中i=l, 2，s，则a是n的正因数的充要条件是a=pj P22psS，其中0 w a, i=l, 2，s .由此可知，n的正因数 的个数为 d(n)=( a+1) ( a2+1)

22、(as+1).例10 称自然数为“完全数”，如果它等于自己的所有不包括自身的正约数的和，例如6 =1 + 2 + 3。如果大于6的“完全数”可被 3整除，证明它必能被 9整除。分析要证明一个大于6且能被3整除的“完全数” 3n,必定是9的倍数，可以从反面考虑假如它不是 9的倍数。此时n不是3的倍数，设集合 A=d |d是n的正约数，则集合A与集合B=3 d |d是n的正约数的并集恰好是3n的正约数集合，“完全数” 3n的所有正 约数的和3n +3n是4的倍数，故n是偶数。所以 晋,n ,殳都是“完全数” 3n的约数。只要 还有其它的正约数，即可以说明3n不是“完全数”。解 设“完全数”等于 3

23、n(n2),假设其中n不是3的倍数，于是3n的所有正约数(包 括它自己)总可以分为两类：能被3整除的正约数和不能被 3整除的正约数，若其中 d是不可被3整除的正约数，则 3d是可被3整除的正约数，且 dt3d是一一对应。从而 3n的所有 正约数的和是4的倍数。又由题意，所有正约数的和(包括自身)为6n，因此，n是2的倍数。因为n 2，所以罟,n,訓1是3n的互不相同的正约数，它们的和等于3n + 13n，与“完全数”的定义矛盾。所以 n必须是3的倍数，即这类“完全数”是 9的倍数。说明本题涉及到两个概念，“完全数”和所有正因数的和。n是完全数，则它的所有正因数的和为2n ,另外，若n = pj

24、 P22PiPsS ,贝U n的所有正因数的和是as(n)=(1+ P1+ P2 + + P11 )(1+ P2+ P； + + P22 )(1+Ps+ p； + + Pss)=P1 j 1Pi 1请思考,能否延此方向解决问题。情景再现9 求所有使p2+2543具有少于16个不同正因数的质数 p。( 2003年泰国数学奥林匹克)10 (1)若n(n N*)个棱长为正整数的正方体的体积之和等于2005,求n的最小值，并说明理由；(2)若n(n N*)个棱长为正整数的正方体的体积之和等于2002 2005,求n的最小值,并说明理由.(2005年江苏)习题131 .对于正整数n ,如果能找到正整数

25、a、b，使n = a + b + ab，则称n为好数”，则在前100个正整数中，共有“好数”()A . 78 个B . 74 个C . 70 个D . 66 个2 .设a为正奇数，则a2 1必是A.5的倍数 B.3的倍数 C.7的倍数 D.8的倍数3 .设n为奇质数，求证：2n 1与2n+1不能同时是质数.100的整数部分末三位数字是几?2001 200150955 .设n是正整数，且4n2+17n 15表示两个相邻正整数的积，求这样的n的值.6 .若26+29+2n为一个平方数，则正整数n =。(2005年江西)7 .证明：任何十个连续正整数中必有至少一个数与其他各数都互质.8 .对任意正整

26、数 n,求证：(n +2) r- ( 12005 + 22005 + +n2005 )。9 .把1 2006这2006个数分成n个小组，使每个数都至少在某一个组中，且第一组中的数没有2的倍数，第二组中的数没有3的倍数，第 n组中没有n+1的倍数，那么，n至少是几?10 .是否存在2006个连续整数，使得每一个都含有重复的素因子，即都能被某个素数的 平方所整除?“情景再现”解答:1选 B。设此六位数为 x= ax 105 + b x 104 + cx 103 + a x 102 + b x 10 + c = 100100 x a+ 10010 x b + 1001 x c = 1001(100

27、a +10 b +c) = 7 x 11 x 13 x (100a + 10 b + c ) , v a , b , c都是整数， 100a + 10b + c也是整数， 7, 11, 13 一定是x的约数。2 .选C. v p + 2d是质数，p、d是正整数， p必是奇数。v p+d是质数，p是奇数， d必是偶数。又 d不能被6整数， d = 6 m + 2或d = 6 m + 4( m Z)，设p = 3k + 1，或p =3 k + 2，或 p = 3 k(k Z)，当 p = 3 k + 1 或 p = 3 k + 2 时，p+d 或 p +2d 中必有一个是 3 的 倍数且大于3，不

28、是质数与已知条件矛盾， p = 3k,而已知p是质数， p = 3,当d=6m+2 时，p + 3d = 3+ 18 m + 6 = 9(2 m + 1)，当 d = 6m + 4 时，p + 3d = 3 + 18 m + 12 = 3(6 m +5), v m Z, 2m + 1 Z, 6m + 5 Z , p + 3d 一定是 3 的倍数。2n2n3n6n10曰疋个既约分数,故当n=3时，该分数是既约分数.这个分数为168113 .解：2n3n10(n5)(n2)2，而当 n 2= 1 时，右(n+8, n+5)=( n+5, 3)=1 ,n26n16(n8)(n2)4设删去最后的数字

29、6后，余下的数为x，若x是m位数，则原数是n = 10 x +6.据题1意有4(10 x + 6) = 6 x 10m + x，解得x=13x 2 x (10m -4)，要使n最小，就是使 m最小，且使2(10 m -4)是13的倍数。取 m = 1 , 2 , 3，逐一检验，知m最小为5 , x = 2 x 7692 = 15384，所求的最小数是 153846。2 n 15. n 是正整数，则 xn yn =(x y)(xn-1+xn-2y+xn-3y2+xyn-2+yn-1)(*)，在(*)中取 x=2,n 1mn 1nnny = 1，并以 2m -1 -代替(*)中的 n,得(22 1

30、) | ( 22 1)。又 2 1=( 22 )2 1=( 2 +1)( 2nn 11)，故(22 +1) | ( 22 1),2n2m于是(2 +1) | ( 2 1)。6. 由于36 = 4 x 9 ,而(4 , 9) = 1 ,所以只要分别证明 2n6n4 n2被4及9整除。将2n 6 n4 n2分解成n2(2n2+ 1)(n2 1)，当n为偶数时，4|n2;当n为奇数时，n2被4除余数为1, 故 4|(n2 1)。故 4|n2(2n2+ 1)(n2 1)。当 n = 3k (k Z)时,9|n2(2n2+ 1)(n2 1); 当 n = 3k 1 (k Z)时，n2被3除余数总是1，所

31、以3|(n2 1)，且2n2被3除余数为2，所以3|(2n2 + 1)，于是 9|(n2 1)(2n2+ 1)，故 9|n2(n2 1)(2n2+ 1)。a2a97. 设 f(a)= a4 + a3 + a2+ a + 1= b2，由 f(a)a4+ a3 +丁 = (a2+ 刁2、f(a)v a4 + a3 + a2 + a + 1 = (a2 + 号 + 1)2 知(a2+ |)2 v b2v (a2+1+ 1)2,所以(2a2 + a)2 v (2b)2 3 时，p2+2543 = p2 1+2544=( p 1)( p+1)+2400+144，质数 p 3，则必为 3k 1型的奇数，p

32、 1、p+1是相邻的两个偶数，且其中必有一个是 3的倍数，所以(p 1)(p+1)是24的倍数，所以p2+2543是24的倍数，p2+2543=2 3+iX 31+jX m，若m 1，共有正因数 (3+i+1) X (1+j+1) X (k+1) 16 个，若 m=1 , 2i X 3j 106，当 j 1，正因数个数不少于16，当j=1 , i 4,正因数个数不少于24，当j=0 , i 5，正因数个数不少于18，所以p 3不满足条件；综上所述，p 2时，正因数个数至少有16个，而p=2时正因数个数为 6，故所求的质数 p是2。10. 解：(1)因为 103=1000,11 3=1331,1

33、2 3=1728,13 3=2197, 12 3 2005 3 X 83,知最大的正方体 棱长只能为9、10、11或12。由于 2005 V 3 X 93, 2005 2 X 93=547 , 2005 93- 2 X 83 0,所以 x工 9。由于 2005 2 X 103=5, 2005 103 93 =276 , 2005 103 83 =493 , 2005 103 2 X73 0,所以 xm 10。由于 2005 113 83 =162 , 2005 113 73 =331 , 2005 113 2 X 63 0,所以 x m 11。由于 2005 123 63 =61 , 2005

34、 123 53 =152 53,所以 xm 12。因此n =3不可能是n的最小值.综上所述，n =3才是n的最小值.(2)设n个正方体的棱长分别是X1 , X2,，Xn，则(X1)3 + (X2)3+ +( Xn)3=2002 2005。由 2002 = 4(mod9) ,43 = 1(mod9)，得2002 2005 三42005 三 4668 X3+1 三(43)668 X 4= 4(mod9)，又当 x N* 时，x3= 0，土 1(mod9),所以(x1)3=4(mod9) , (x1)3+(x2)3=4(mod9) , (x1)3+(x2)3+(x3)3=4(mod9)，式模9,由、

35、可知，n 4.而 2002=10 3+103+1 3+1 3,贝U 2002 2005 =2002 2004 X (103 + 103+1 3+1 3)=(2002 668)3 X (103+103+1 3+1 3)=(2002 668 X 10) 3+(2002 668 X 10)3+(2002 668)3 +(2002 668)3。因此n =3为所求的最小值.“习题16”解答：1 .解(a + 1)(b + 1) = n + 1,即只要n + 1为合数，贝U n为好数” .n + 1为质数则n不 是“好数” 在2101中质数共26个，故选B .2.解设 a=2k 1，贝U a2仁(2 k 1)2仁2k(2k 2)=4 k(k 1)为 8 的倍数，故选 D3 .证明 T n 3 , 2n 13 , 2n+13 .2n 1 , 2n, 2n+1三个连续数中必有一个是3的倍数，但2n不是3的倍数，故2n 1 ,2n + 1中必有一个为3的倍数，且此二数均大于3，即此3的倍数即不是质数.4 .解:2001100 910 91020015095(20015095)(2001 50 95) 91050 小52001950 小52001950 小5200199.505 3 时 n0 .1 k当 k 1，知 n