本科毕业论文-同余在中学数学竞赛中的应用.doc

分类号 O12 陕西师范大学学士学位论文同余在中学数学竞赛中的应用作 者 单 位 陕西师范大学继续教育学院指 导 老 师 许 汪 涛 作 者 姓 名 于 小 强 专 业、班 级 2006 级 数 学 专 升 本提 交 时 间 2007年11月 同余在中学数学竞赛中的应用于小强（继续教育学院2006级）指导老师：许汪涛摘 要本文写的是自己在做题中得出的一些关于同余的性质。有些给出了证明，谈了应用，有些只给出了证明。关键词数论 同余 应用 数学竞赛正文一 准备知识1定义：设m是一个给定的正整数，如果两个数a,b用m除所得的余数相同，则称a,b对模m同余。记为ab(modm)。2 同余的基本性质（1）ab(m)mab；（2）若ab(m) bc(m) 则ac(m)；(3) 若ab(m) ,cd(m),则acbd(m) acbd(m)；(4) acbc(m) c0,则ab()，特别地，若（m,c）1 则ab(m)；(5) ab(m) 而dm,(d0) 则ab(d)；(6) 若ab(m),c是正整数, acbc(m)；(7) 若ab(m),若ab(m),则ab(m,m),特别地，若（m,m）1, 则ab(mm)；(8) 若ab(m),则（a,m）(b,m)；(9)若ab(m),i=1,2,n,则ax+ax+ax+abx+bx+bx+b(m),特别地，设= cx+cx+cx+c(cz), 若ab(m),则(m)；（10）若1，（a,m）1，则存在使得1(m)，我们把称为是对模的逆，记作(m)3 定理（1）欧拉定理 若（a,m）=1,则a1(m). (2)费尔马小定理 若p为素数，则aa(p).二 主要结论及应用命题1 一个数和它各位上的数字之和关于模9同余。证明 任一个正整数aaaa(十进制表示) 也可表示为a+a+a+a,而a+a+a+aa+a+a+a(), a+a+a+a为它的各位数字之和.命题得证例1设十进制数的各位数字之和为A，而数A的各位数字之和为B，求B的各位数字之和。解 如果n有k位数，那么它的各位数字之和最大为9K，注意到=因此，至多有17777位数。所以A17777=159993同理可得B59=45，并且B的各位数字之和C3+9=12由命题1 由费尔马小定理1应用这个结果并且注意到=我们有7而小于12并且和7同余以9为模的数只有7。因此C=7.命题1在实际应用中有很大的用处。能知道一个数被9除的余数。判断乘法算式的对错计算像例1这一类题。命题2 如果一个等式的两边都取整数值，则等式的两边必对任意非零整数都同余。即：，均取整数值，且=，k为任意非零整数，则例2 设是异于2，5，13的任一正整数，求证在集合2，5，13，d中可以找到两个不同元素a,b使得ab-1不是完全平方数(1986年第二十七届国际数学奥林匹克竞赛第一题) 证 因为25-1= 213-1= 513-1= 所以我们要证集合2d-1,5d-1,13d-1有一个数不是完全平方数。用反证法。假设所有的数都是完全平方数，2d-1= 5d-1= 13d-1= 显然a是奇数，不妨设a=2x-1 那么d=2x(x+1)+1 因此d1(4)，而b,c是偶数，故可设b=2y c=2z 由于d=因此z,y的奇偶性相同，所以z-y0(4)而矛盾。命题3记整数的个位数为，为整数，则=证明：事实上的个位数为0、1、2、3、4、5、6、7、8、9的个位数为0、1、4、9、6、5、6、9、4、1；的个位数为0、1、8、7、4、5、6、3、2、9；的个位数为0、1、6、1、6、5、6、1、6、1；的个位数为0、1、2、3、4、5、6、7、8、9；的个位数为；0、1、4、9、6、5、6、9、4、1；的个位数为；0、1、8、7、4、5、6、3、2、9；的个位数为；0、1、6、1、6、5、6、1、6、1；的个位数为；0、1、2、3、4、5、6、7、8、9； 特别地=例3(第七届美国数学邀请赛第9题) 欧拉的一个猜想在1960年被美国的数学家推翻，他们证实了存在正实数，使得1335+1105+845+275=，求的值。解：分以下几步解决问题：1先对进行初步估值1.33510，1.1510，0.8451，0.27511335+1105+845+27520051332002求出的个位数1335+1105+845+275=有命题3可知= 3求的十位数由结论2，等式两边对3同余1335+1105+845+275n5(3)而1335+1105+845+27515+25+05+050(3)能被3整除能被3整除=144或174仍由结论2，等式两边对7同余而1335+1105+845+2752(7)n52(7)又14452(7)；17456(7)=144例4求的个位数n.解：由结论3：的个位数与的个位数是一样的即的个位数是1的个位数是1这一命题适合计算与个位数字有关的一些题目。 命题4如果两个式子均取整数，若它们对某一非零整数不同余，则这两个式子必定不相等。即：，均取整数值，为任意非零整数，且与对不同余，则=例5(第八届美国数学奥林匹克第1题) 求不定方程+ +=1599的一切(如果有的话)非负整数解，不计排列次序。解： (i=1,2,14) 为非负整数=或 若 =则16| 即0若则=+1一定为偶数1存在整数0,14使得+ +r即+ +被16除的余数在014之间但另一方面159915(mod16)由命题4，+ +与1599不可能相等，所以原方程无解。例6设正整数a,b使15a+16b和16a-15b都是正整数的平方，求这两个平方数较较小的数能够取到的最小值（第三十七届国际数学奥林匹克第四题）解：设15a+16=x 16a-15b=y,x,yN转为讨论不定方程组的正整数解的性质.由15a+16b=x 16a-15b=y可知+(+)(+)481(+)481+注意到4811337 所以我们有（1）+0（13） 若x0（13）则y0（13）若x0（13）y0（13）此时由费儿马定理知1x-1(13)矛盾。故x0(13) 进而y0(13)(2) +0（37）同上若x0（37）则y0（37）若x0（37）y0（37）此时1x-1（mod37）矛盾故x0(37) 进而y0(37)综上可知xy0()且xy0(37)所以xy0(481)即x,y481另一方面令a48131 b481 可知xy481综上可知 所求最小值为.命题5设是正整数,并设是一个与互质的正整数.用表示模的阶,即是使得1()成立的最小正整数,则对任意使得1(q)的正整数,一定有.证明:由的最小性,我们能写成+,其中和都是正整数且1,0则1(q),由的最小性知,因此得证.例6数和的最后三位数相同,试求出正整数和,使得取得最小值,这里1.解 由于和的最后三位数相同,所以我们有-=(-1)0(),由分解式=且-1是奇数,我们可得到,由1978=2989,我们有3.显然=+,取,我们的方法就是使最小化,并求的最小值,使得1,因为(1978,5)=1,所以问题就转化为求的尾数的阶,我们已经知道一个与同余的数的尾数阶是的一个约数,其中是欧拉函数,那么就有=,因此,1,则1,但是,因为的阶是4,那么就有由-,我们有61,因此我们可排除=4的情形,又因为,所以=或,计算可得-,所以我们有,.这个命题能减少很多运算。对于本道题而言，如果不应用这个命题，计算量很大，因为100的约数有9个：1，2，4，5，10，20，25，50，100，就要逐个检验，而应用此命题后，100的约数，4的倍数是4，20，100一下子就缩小到3个，因此只需算3次。例7：数列，定义如下=（n=1,2,）求与此数列的每一项都互质的所有正整数。解：满足条件的正整数只有1下面证明：对任意的质数，它一定是数列 的某一项的因数。对于和，它们都是=48的因数。对于每一个大于3的质数，因为=1，=1，=1，所以由费尔马小定理1，1，1。所以+即+6。故=+-10。也就是说，对任意大于1的正整数，它必有一个质因数，则1；若5，则1，故大于1的正整数都不符