初等数论总复习题及知识点总结(2)

除问题的方法。

本章的许多问题都围绕着整除而展开，读者应对整除问题的解决方法作一简单的小结。

五、例子选讲

补充知识

①最小自然数原理：自然数的任意非空子集中一定存在最小自然数。 ②抽屉原理：

（1）设n是一个自然数，有n个盒子，n+1个物体，把n+1个物体放进n个盒子，至少有一个盒子放了两个或两个以上物体；

（2）km+1个元素，分成k组，至少有一组元素其个数大于或等于m+1； （3）无限个元素分成有限组，至少有一组其元素个数为无限。 ③梅森数：形如2n-1的数叫梅森数，记成Mn=2n-1。

2④费尔马数：n为非负整数，形如2n?1的数叫费尔马数，记成Fn=22?1。

nk1⑤设n=p1...pk，设n的正因子个数为d(n)，所有正因子之和为?(n)，则有

??d(n)?(?1?1)?(?2?1)...(?k?1) ??1?1?12?1pkk?1p1?1p??12?(n)??...P1?1P2?1Pk?1 ⑥有关技巧

1. 整数表示a=a0×10n+a1×10n-1+…+an，

a=2kb(b为奇数) 2.整除的常用方法

a. 用定义

b. 对整数按被n除的余数分类讨论 c. 连续n个整数的积一定是n的倍数 d. 因式分解

an-bn=(a-b)M1, an+bn=(a+b)M2, 2 n e. 用数学归纳法

6

f. 要证明a|b，只要证明对任意素数p，a中p的幂指数不超过b中p的幂指数即可，用p(a)表示a中p的幂指数，则a|b?p(a)?p(b) 例题选讲

例1.请写出10个连续正整数都是合数. 解: 11!+2，11!+3，??，11！+11。

例2. 证明连续三个整数中，必有一个被3整除。

证：设三个连续正数为a，a+1，a+2，而a只有3k，3k+1，3k+2三种情况，令a=3k，显

然成立，a=3k+1时，a+2=3(k+1)，a=3k+2时，a+1=3(k+1)。

例3. 证明lg2是无理数。

证：假设lg2是有理数，则存在二个正整数p，q，使得lg2=

p，由对数定义可得10p=2q，q则有2p·5p =2q,则同一个数左边含因子5，右边不含因子5，与算术基本定理矛盾。∴lg2为无理数。

例4. 求(21n+4，14n+3)

解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1

例5. 求2004!末尾零的个数。 解：因为10=2×5，而2比5多， 所以只要考虑2004！中5的幂指数，即

2004??2004??2004??2004??2004?5（2004！）=???????????4???5??499

?5??25??125??5??5?

例6.证明（n!）(n-1)!|(n!)!

证：对任意素数p,设（n!）(n-1)!中素数p的指数为?， （n!）!中p的指数β，则

7

??(n?1)!k????n???1??pk?，??(n?1)!????n!???k?1??pk??,?(nx)?n(x) ?????n!?????????(n?1)!k???n(n?1)!???(n?1)!??n!????n!??1??pk??k?1??pk??k?1??pk???k?1??pk???? 即???，即左边整除右边。

例7. 证明2003|（20022002+20042004-2005） 证：∵ 20022002=（2003-1）2002=2003M1+1

20042004=（2003+1）2002=2003M2+1 ∴20022002+20042004-2005=2003（M1+M2-1） 由定义2003|（20022002+20042004-2005）

例8. 设d(n)为n的正因子的个数，? (n)为n的所有正因子之和，求d(1000)，解：∵ 1000=23·53

∴ d(1000)=(3+1)(3+1)=16，? (1000)=24?154?12?1?5?1

例9. 设c不能被素数平方整除，若a2|b2c，则a|b 证：由已知p(c)?1，且p(a2)?p(b2c)

∴ 2p(a)?2p(b)+p(c) , ∴ p(a)?p(b)+p(c)2

即p(a) ?p(b) , ∴ a|b

例10. 若Mn为素数，则n一定为素数。 证：若n为合数，则设n=ab，（1

∴ 2ab-1=(2a)b-1=(2a-1)M为合数，与Mn为素数矛盾， ∴ n为素数。

例11. 证明对任意m,n，m≠n, (Fn,Fm)=1。 证：不妨设n>m，则Fn?1n-2=（22?1）（22n?1?1）=(Fn?1n-1-2) （22?1）

(1000)。 8

?= Fn-1Fn-2??Fm- F0

设（Fn,Fm）=d,则d|Fn, d|Fm?d|2 但Fn为奇数，∴d=1, 即证。

例12. 设m,n是正整数。证明

(2m?1,2n?1)?2(m,n)?1

证 : 不妨设m?n。由带余数除法得

m?q1n?r1,

0?r1?n.

我们有

2m?1?2q1n?r1?2r1?2r1?1?2r1(2q1n?1)?2r1?1

nqrnmn由此及2?1|21?1得,(2?1,2?1)=(2?1,21?1)

n注意到(m,n)?(n,r1),若r1?0,则(m,n)?n,结论成立.若r1?0,则继续对(2n?1,2r1?1)作同样的讨

论，由辗转相除法知，结论成立。显见，2用任一大于1的自然a代替，结论都成立。

例13. 证明：对任意的正整数n，成立如下不等式lgn?klg2。

其中lgn是数n的以10为底的对数，k是n的不同的素因数（正的）的个数。

证：设n是大于1的整数（如果n=1，上述不等式显然成立，因k=0），p1,p2,...,pk 是n的k个

相异的素因素。n的素因数分解式为

lkl1l2n?p1p2...pk.(li?1,i?1,2,...,k) , 由于pi?2,(i?1,2,...,k)，从而

lkl1l2n?p1p2...pk?2l1?2l2?...?2lk?2l1?l2?...?lk，

而l1?l2?...?lk?k，故n?2k。

将上述不等式取对数（设底a?1）,则有logan?kloga2。 特别有lgn?klg2。

例14. 试证明任意一个整数与它的数字和的差必能被9整除，并且它与它的数字作任意调后

9

换后所成整数的差也能被9整除。

证： 设整数m的个位、十位、百位?的数字分别为a1,a2，?，an，则m可表作：

m?a1?10a2?100a3?...?10n?1an

n?1个????(a1?a2?a3?...?an)?(9a2?99a3?...?99...9an) n?1个????(a1?a2?a3?...?an)?9(a2?11a3?...?11...1an) n?1个???所以m?(a1?a2?a3?...?an)?9(a2?11a3?...?11...1an)

因为a2，a3,?，an都是整数，所以任一整数与其数字之和的差必能被9整除。 再设将a1,a2，?，an按任一种顺序排成a'1,a'2，?，a'n，并令

??a1?a2?...?an，?'?a'1?a'2?...?a'n，m?a1?10a2。

?...?10n?1an，

m'?a'1?10a'2?...?10n?1a'n根据前面证明的结果，知存在整数A，B，使m??因为???'，所以m?m'???9A??'?9B?9(A?B)。

?9A,m'??'?9B.

由于A-B是整数，这就证明了m?m'能被9整除。

注：若对某个整数k(1?k?n)，有a'k?0，但当k?i?n时，a'i?0，则此时m'为整数：

a'2a'1。 m'?a'1?10a'2?...?10k?1a'k,即m'?a'k...如前证，此时结论正确。又当m为负整数及零时，结论显然正确。

? 第二章 不定方程 一、主要内容

一次不定方程有解的条件、解数、解法、通解表示，不定方程x2+y2=z2通解公式、无穷递降法、费尔马大定理。 二、基本要求

1、了解不定方程的概念，理解对“解”的认识，掌握一次不定方程ax?by?c有解的条件，能熟练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库初等数论总复习题及知识点总结(2)在线全文阅读。