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
证