湖北师范学院2007届数学系学士学位论文(设计)5
5、一个整数被4，25整除的充要条件是它的末二位能被4，25整除. 6、一个整数被8，125整除的充要条件是它的末三位能被8，125整除. 例6:证明:对于整数x与y, 2x?3y与9x?5能同时被17整除或不可整除. 证:记u?2x?3y, v?9x?5,则有3v?5u?17x
即3v?5u?17x (1)
5u?3v?17x
(2)
若对x0,y0?z, 17?u0.其中u0?2x0?3y0,由(1) 知17?3v0,其中v0?9x0?5y0.又(17,3)=1,所以17?v0.
同理可证,对x1,y1?z,17?v1,其中v1?9x1?5y1,则 17?u1,其中u1?2x1?3y1.
证毕.
【分析】将本题加以推广:用ax?by,cx?dy代替2x?3y与9x?5y. 令u?ax?by,v?cx?dy.设ad?bc?0 消去y,du?bv?(ad?bc)x?du?bv?sx,bv?du?sxabcdx.记s?abcd.
若(d,s)?(b,s)?1,则对同样的x,y,u与v同时被s整除(或同时不被s整
除)
若(a,s)?(c,s)?1,结论成立. 例6中
2395??17,而(3,?17)?(5,?17)?1,(2,?17)?(9,?17)?1.所以例
4成立.
例7: 1000!的末尾有几个零?
!标准分解式中2与5这两个素数的指数,若解:考虑1000的1000!?2r15r2A,A?N,A不能被2与5整除,则1000!中末尾有r个零, r是r1和r2中
较小者.
在1,2,3,
?,1000中,有200个数能被5整除,在这200个数中,有40个能被52整
5
湖北师范学院2007届数学系学士学位论文(设计)6
除,在这40个数中,有8个能被53整除,在这8个数中,有1个能被54整除.
不大于1000的自然数中没有能被5的5次幂或更高次幂整除的数. 可见在1000!的标准分解式中,5的指数r2?200?40?8?1?249. 显然r1?r2,所以r?249,即1000!的末尾有249个零.
4.最大公因数
和整除性一样，二个数的最大公约数实质上也是用等号来定义的，因此在解决此类问题是如果有必要的话可化为等式问题.最大公约数的性质中最重要的性质之一为：若a=bq+c，则一定有（a，b）=（b，c），这就是求二个整数的最大公约数的理论根据.
最小公倍数实际上与最大公因数为对偶命题.特别要指出的是a和b的公倍数是有无穷多个.所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数的最小的正整数.这一点实际上是应用自然数的最小自然数原理.即自然数的任何一个非空子集一定有一个最小自然数存在.最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题. 两者的关系为
a,b?N,
[a,b]?ab(a,b)
例8：对于任意的非负整数n，求形式为 7n?2?8n?2?57的一切数的最大
公因子.
在解答初等数论的习题中，如果我们把题目有关的概念，例如整除，最大公因子，互素等用等式表示出来，再经过这些等式的恒等变形，常常能够找到解题的方法.
解:当n?0时, 7(k?1)?2?82(k?1)?1?57; 假设n?k时, 57|7k?2?82k?1; 当n?k?1时,
7(k?1)?2?82(k?1)?1?7k?2?7?82k?1?8
k?k?22k?12k2?1?8)?8(8? ?7(77??)278??k?212k?8
7 6
湖北师范学院2007届数学系学士学位论文(设计)7
2k?1 ?57q?(?78??647
k?2)?57 7k?2k?22k?1k?2 ?57q?(?78??77?)] ?57q?[7k(?27?2k?18?)?57 7 ?57p (p,q?N)
故形为7n?2?82n?2的一切数的最大公因子为57.
例9:证明:若a,b?N,那么等差数列a,2a,3a,?ba中能被b整除的项数等于a与b的最大公约数.
证明:设(a,b)?d,于是a?dr,b?ds,r,s?N.(r,s)?1.a,2a,3a,?ba被b整除之后为
rs,
2rs,?(ds)rs
1s由于(r,s)?1.上式中各项为整数者的项数,仅为共计d项,证毕.
,
2s,?,
dss中为整数的项数,所以
5.抽屉原理在数论中的应用
抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。
把3个苹果放进2个抽屉里，一定有一个抽屉里放了2个或2个以上的苹果。这个人所皆知的常识就是抽屉原理在日常生活中的体现。用它可以解决一些相当复杂甚至无从下手的问题。
原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。
原理2：把m个元素任意放入n（n≤m）个集合，则一定有一个集合至少要有k个元素。其中 k＝m/n（当n能整除m时） 或k＝〔m/n 〕＋1 （当n不能整除m时）， 这里〔m/n 〕表示不大于m/n的最大整数，即m/n的整数部分。 原理3：把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。
7
湖北师范学院2007届数学系学士学位论文(设计)8
原理2也可以变为：把m个元素任意放入n（n≤m）个集合，则一定有一个集合至多要有k个元素。其中 k＝〔m/n 〕 ，这里〔m/n 〕表示不大于m/n的最大整数，即m/n的整数部分。 应用抽屉原理解题的步骤 :
第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”，什么可作“抽屉”。
第二步：制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路。
第三步：运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决。 利用上述原理容易证明：
“任意7个整数中，至少有3个数的两两之差是3的倍数。”
因为任一整数除以3时余数只有0、1、2三种可能，所以7个整数中至少有3个数除以3所得余数相同，即它们两两之差是3的倍数。 1958年6/7月号的《美国数学月刊》上有这样一道题目：
“证明在任意6个人的集会上，或者有3个人以前彼此相识，或者有三个人以前彼此不相识。”
这个问题可以用如下方法简单明了地证出：
在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一 条蓝线。考虑A点与其余各点间的5条连线AB，AC，...，AF，它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色，不妨设AB，AC， AD同为红色。如果BC，BD，CD3条连线中有一条（不妨设为BC）也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的3个人以前彼此相 识：如果BC、BD、CD3条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代表的3个人以前彼此不相识。不论哪种情形发生，都符合问题的 结论。
例10：从1～100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个数是另一个数的整数倍.
8
湖北师范学院2007届数学系学士学位论文(设计)9
【分析】现在的‘苹果’数定了51个,我们怎么来构造出符合要求的50层抽屉来?显然抽屉的构造只能从1～100个数中选取,从整数倍这点提示我们,在构造抽屉时应重点考虑这个问题.有一种方法,我们可以按奇数的2的n次方的倍数分组(因为刚好50个奇数).即
{1,2,4,6,?,64}; {3,6,12, ?,96}; {5,10,20,40,80}; {7,14,28,55}; ? {97}; {99}.
共50组.任取51个数,必有两个数落在同一组里.显然,同一组的两个数,必定有一个数是另一个数的整数倍.
在这里运用了构造抽屉的思想,在整除问题中有时题目太复杂,构造抽屉可以缩小题目的范围,达到简化的目的.
例11: a,b,c,d为任意给定的整数,求证:以下六个差数
b?a,c?,a?d,a?c,12整除. b?d,的乘积一定可以被?bdc证明 把这6个差数的乘积记为p,我们必须且只需证明:3和4都可以整除p,
以下分两步进行.
第一步,把a,b,c,d按以3为除数的余数来分类,这样的类只有三个,故知
a,b,c,d中至少有2个除以3的余数相同,例如,不妨设为a,b,,这时3可整除
b?a,从而3可整除p.
第二步,再把a,b,c,d按以4为除数的余数来分类,这种至多有四个,故知
a,b,c,d中有两个数除以4的余数相同.那么与第一步类似,我们立即可作出4
可整除p的结论.设a,b,c,d四数除以4的余数不同,由此推知, a,b,c,d之中必有二个奇数(不妨设为a,b),也必有二个偶数(设为c,d),这时b?a为偶数,d?c也是偶数,故4可整除(b?a)(d?c),自然也可得出4可整除p.
9