e. 用数学归纳法
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=
ppqp，由对数定义可得10=2，则有2·5p q=2,则同一个数左边含因子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?q
例6.证明（n!）(n-1)!|(n!)!
证：对任意素数p,设（n!）(n-1)!中素数p的指数为?， （n!）!中p的指数β，则
??n???n!??，??(n?1)!???(n?1)!????,?(nx)?n(x) k??k??k?1?p?k?1?p??n!???kk?1??p????n(n?1)!??????????(n?1)!?n!?k?1?pk?k?1?pk?????????(n?1)!??n!k?k?1???p???? ??即???，即左边整除右边。
例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)。 解：∵ 1000=23·53
∴ d(1000)=(3+1)(3+1)=16，?24?154?1? (1000)=
2?15?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(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-2=（22n?1p(c) 2（2?1） 2n?1?1）=(Fn-1-2) （22n?1?1） = 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 由此及2n?1|2q1?1得,(2m?1,2n?1)=(2n?1,2r1?1) nr注意到(m,n)?(n,r1),若r1?0,则(m,n)?n,结论成立.若r1?0,则继续对(2n?1,21?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特别有lgn?klg2。 ?2k。 将上述不等式取对数（设底a?1）,则有logan?kloga2。 例14. 试证明任意一个整数与它的数字和的差必能被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???9A,m'??'?9B. 因为???'，所以m?m'???9A??'?9B?9(A?B)。 由于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为负整数及零时，结论显然正确。 第三章 同余 一、 主要内容 同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2，3，4，5，6，7，8，9，11，13的整除规律 二、 基本要求 通过本章的学习，能够掌握同余的定义和性质，区别符号：“三”和=”之间的差异。能利用同余的一些基本性质进行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质及构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值，掌握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理证明有关的整除问题和求余数问题。能进行循环小数与分数的互化。 三、难点和重点 （1）同余的概念及基本性质 （2）完全剩余系和简化剩余系的构造、判别 （3）欧拉函数计算、欧拉定理、费尔马小定理的证明及应用 （4）循环小数与分数的互化 （5）特殊数的整除规律。 四、自学指导 同余理论是初等数论中最核心的内容之一，由同余定义可知，若a≡b(mod m)，则a和b被m除后有相同的余数。这里m为正整数，一般要求m大于1，称为模，同余这一思想本质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故同余还有二个等价的定义：①用整除来定义即 m∣a-b 。②用等号来定义a=b+mt 。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模m1，a和b未必会同余。 从定义上看，同余和整除是同一个事情，但引进了新的符号“三”后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号“三”和等号“=”相比，在形式上有几乎一致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法： （i）模不改变的除法，若ak≡bk(mod m) ，(k,m)=1，则a≡b(mod m) (ii)模改变的除法, 若ak≡bk(mod m) (k,m)=d,则a≡b?mod??m?? a?这一点读者要特别注意。 完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对于更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，由于二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模m的一个完全剩余系的条件有二条为 （1） 个数=m （2） 关于m两两不同余 另外要能用已知完全剩余系构造新的完全剩余系。即有定理 设（a，m）=1，x为m的完全剩余系，则ax+b也是m的完全剩余系。 当(m1,m2)?1时，能由m1的完全剩余系和m2的完全剩余系，构造m1m2完全剩余系。