当前位置:首页 > 学科相关 > 数学 > 正文
 

数学数论

发布时间:2024-03-29 02:25:54 影响了:

小编语:为你精心整理的数学数论,希望对你有帮助! 如果喜欢就请继续关注我们博文学习网(www.hnnscy.com)的后续更新吧!

数学数论篇一:数学竞赛中的数论问题 (习题部分)

数学竞赛中的数论问题

第二部分 数论题的范例讲解

主要讲几个重要类型:奇数与偶数,约数与倍数(素数与合数),平方数,整除,同余,不定方程,数论函数等.重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容.

一、奇数与偶数

整数按照能否被2整除可以分为两类,一类余数为0,称为偶数,一类余数为1,称为奇数.偶数可以表示为2n,奇数可以表示为2n-1或2n+1.一般地,整数被正整数m去除,按照余数可以分为m类,称为模m的剩余类Ci=xx≡i(modm),从每类中各取出一个元素ai∈Ci,可得模m的完全剩余系(剩余类派出的一个代表团),0,1,2,

{}

,m-1称

为模m的非负最小完全剩余系.

通过数字奇偶性质的分析而获得解题重大进展的技巧,常称作奇偶分析,这种技巧与分类、染色、数字化都有联系,在数学竞赛中有广泛的应用. 关于奇数和偶数,有下面的简单性质:

(1)奇数≠偶数.

(2)偶数的个位上是0、2、4、6、8;奇数的个位上是1、3、5、7、9. (3)奇数与偶数是相间排列的;两个连续整数中必是一个奇数一个偶数;.(4)奇数个奇数的和是奇数;偶数个奇数的和是偶数;偶数跟奇数的和是奇数;任意多个偶数的和是偶数.

(5)除2外所有的正偶数均为合数;

(6)相邻偶数的最大公约数为2,最小公倍数为它们乘积的一半. (7)偶数乘以任何整数的积为偶数.

(8)两数和与两数差有相同的奇偶性,a+b≡a-b(mod2). (9)乘积为奇数的充分必要条件是各个因数为奇数. (10)n个偶数的积是2的倍数.

(11)(-1)=1的充分必要条件是k为偶数,(-1)=-1的充分必要条件是k为奇数.

(12)(2n)≡0(mod4),(2n-1)≡1(mod4),(2n-1)≡1(mod8). (13)任何整数都可以表示为n=2??

例1 (1906,匈牙利)假设a1,a2,数,则乘积

(a1-1)(a2-2)

m

2

2

2

k

k

n

(2k-1).

,n的某种排列,证明:如果n是奇

,an是1,2,

(an-n)

是偶数.

类似题:

例1-1(1986,英国)设a1,a2,

,a7是整数,b1,b2,,b7是它们的一个排列,证明

(a1-b1)(a2-b2)(a7-b7)是偶数.

(a1,a2,

例1-2π的前24位数字为π=3.14159265358979323846264,记a1,a2,24个数字的任一排列,求证(a1-a2)(a3-a4)

,a7中奇数与偶数个数不等)

,a24为该

(a23-a24)必为偶数.

(暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等)

例2 能否从1,2,

,15中选出10个数填入图的圆圈中,使得每两个有线相连的圈中的

,14?

数相减(大数减小数),所得的14个差恰好为1,2,

例3 有一大筐苹果和梨分成若干堆,如果你一定可以找到这样的两堆,其苹果数之和与梨数之和都是偶数,问最少要把这些苹果和梨分成几堆?

例4 有n个数x1,x2,

,xn-1x,n,它们中的每一个要么是1,要么是-1.若

1n

x1x2+x2x3+

+

+n-xx+nx1x0=,求证4|n.

例5 n个整数a1,a2,

,an-1,an,其积为n,其和为0,试证4|n.

例6 在数轴上给定两点1

内任取n个点,在此n+2个点中,每相邻两点连一线段,可得n+1条互不重叠的线段,证明在此n+1条线段中,以一个有理点和一个无理点为端点的线段恰有奇数条.

二、约数与倍数

最大公约数与最小公倍数的求法. (1)短除法.

(2)分解质因数法.设

a=p1α1p2α2b=p1β1p2β2

pkαk,αi≥0,i=1,2,pkβk,βi≥0,i=1,2,

,k, ,k.

记 γi=min{αi,βi},δi=max{αi,βi}, 则 (a,b)=p11p2

γ

γ2

pkγk, pkδk.

=(rn-1,rn)=(rn,0)=rn.

[a,b]=p11p2

δ

δ2

(3)辗转相除法

(a,b)=(b,r)=(r1,r2)=

例7 (1)求(8381,1015),[8381,1015]; (2)(144,180,108),[144,180,108].

例8 正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9,则

n的最小值为.

例9 有两个容器,一个容量为27升,一个容量为15升,如何利用它们从一桶油中倒出6升油来?

例10 对每一个n≥2,求证存在n个互不相同的正整数a1,a2,

,an,使

ai-ajai+a,对任意的j

i,j∈{1,2,,n},i≠j成立.

例11 (1959,IMO21n+4

1-1)证明对任意正整数n,分数14n+3

不可约.

例12 不存在这样的多项式 f(n)=am

m-1

mn+am-1n

+

+a1n+a0,

使得对任意的正整数n,f(n)都是素数..

数学数论篇二:11数论的几个重要定理

11 数论的几个重要定理

欧拉定理、费马小定理、威尔逊定理及中国剩余定理是数论的四大定理,它们是解决数论问题的重要工具。下面介绍这几个定理在竞赛数学中的应用方法。 1. 基本原理

定理1(欧拉定理) 设m为大于1的整数,(a,m)=1,?(m)为欧拉函数,则

a?(m)≡1(modm).

证 设r1,r2,…,r?(m)为模m的一个简化剩余系,因为(a,m)=1,所以

{}

{ar,ar,…,ar}也是模m的一个简化剩余系,从而有

1

2

?(m)

(ar1)(ar2)…(ar?(m))≡r1r2…r?(m)(modm),

即a?(m)(r1r2…r?(m))≡r1r2…r?(m)(modm) (1)

因为(r1r2…r?(m),m)=1 ,所以由(1)得 a

?(m)

≡1(modm).

定理2(费马小定理) 设p是素数,(a,p)=1,则

ap-1≡1(modp).

证 因为p是素数,所以?(p)=p-1,由欧拉定理知

a?(p)≡1(modp),

∴ a

p-1

≡1(mopd. )

推论 设p为素数,a为整数,则

ap≡a(modp)(2)

证 当pa时,(2)式显然成立.当p不能整除a时,因为p为素数,所以(a,p)=1.由定理2得 a

p

p-1

≡1(mopd,)

∴ a≡a(modp. )

定理3(威尔逊定理) 若p为素数,则

(p-1)!≡-1(modp).

…,p,-证 ?a∈{2,3

2(a,p)=1,所以{a,2a,…,(p-1)a}也是模p的简化},因为

剩余系,故存在唯一的b∈{1,2,…,p-1},使得

ba≡1(modp)(1)

∵ a∈{2,3,…,p-2},∴ b≠1,b≠p-1.若b=a,则

a2≡1(modp)

∴ (a-1)(a+1)≡0(modp). ∴ a≡1或-1(modp),

这与a∈{2,3,…,p-2}矛盾.综上即知b∈{2,3,…,p-2}且b≠a.

将{2,3,…,p-2}中的数按(1)式两两配对,得

2?3?4?…?(p-2)≡1(modp),

∴ (p-1)!≡-1(modp).

定理4(中国剩余定理) 设m1,m2,…,mk是k个两两互质的正整数,m=m1m2…mk,

Mi=

m

,i=1,2,…,k,则同余式组 mi

?x≡a1?x≡a?2??……??x≡ak

有唯一解

(modm1)(modm2)……(modmk)

(1)

x=M1'M1a1+M2'M2a2+…+Mk'Mkak(modm)(2)

其中Mi'Mi≡1(modmi),i=1,2,…,k.

证 容易验证(2)是(1)的解.又若x',x''均是(1)的解,则对于i=1,2,…,k,有

x'≡ai(modmi)

x''≡ai(modmi),

≡0从而有 x'-x''

(modm)m1,m2,…,mk两两互质,从而有 i,又因为

x'-x''≡0(modm),

) 即 x'≡x''(modm,

所以x'与x''是同余式组(1)的相同解. 设m>1,(a,m)=1,则由欧拉定理知a

?(m)

≡1(modm),我们把满足条件

ar≡1(modm)

的最小正整数r称为a对模m的阶,或称为a对模m的指数.关于a对模m的阶,我们有如下结论.

定理5 设m>1,(a,m)=1,a对模m的阶为n0,n为正整数.若a≡1(modm),则n0n.

证 由带余除法知,存在非负整数q及r,使得

n

n=qn0+r,0≤r<n0.

所以 1=a=a

n

qn0+r

=(an0)qar≡ar(modm),

由于r<n0,由n0的最小性知r=0,所以n0n.

2. 方法解读

用上述定理解题,除应掌握数论解题的基本方法外,还应对这几个定理的用途有一定的 认识.一般说来,欧拉定理与费马小定理提供了降幂与归1的工具.威尔逊定理提供了处理连续整数的积的方法.中国剩余定理提供了某些存在性问题的构造方法.定理5提供了由方幂的指数导出整除关系的途径.

例1 求使2-1为7的倍数的所有正整数n. .

解 ∵ 2≡2(mod7),2≡4(mod7),2≡1(mod7),

1

2

n

3

kkN∈)+. 所以2对模7的阶为3.又因为2≡1(mod7),所以由定理5知 3n,即n=3(

例2 设整数a,b,c满足a+b+c=0,记d=a数.

证 ∵ a≡a(mod2), ∴ a∴ a

2011

n

2011

2011

+b2011+c,求证d不是素

2

≡a(mod2)同理知 b2011≡b(mod2),c2011≡c(mod2), +b2011+c2011≡a+b+c≡0(mod2),

2011

∴ 2d.

又由费马小定理知,a≡a(mod3),

3

∴ a

2011

≡a2010a≡(a3)670a≡a670a≡a669a2≡a3?223a2

≡a223a2≡a224a≡a78a≡a26a≡a27≡a9≡a3≡a(mod3),

同理可证 b∴ a

2011

2011

+b2011+c2011≡a+b+c≡0(mod3),

∴ 3d. 又∵ (2,3)=1,∴ 6d,所以d不是素数.

例3 证明:数列1,19,119,1119,11119,…中有无穷多个合数.

证 因为19是素数,(10,19)=1,由费马小定理知 10≡1(mod19),所以对于任 意的正整数n,有

18

∴ 10

18n

-1≡0(mod19),

∴ 9?11…1≡0(mod19),

18n个1

∵ (1(出自:WwW.HNNscy.Com 博 文学习 网:数学数论)9,9)=1, ∴ 19…1,∴ 19…119,即19…119.

18n个1

18n个1

18n个1

由于正整数n有无穷多个,所以数列中有无穷多项被19整除,故数列中有无穷多项为合数.

例4(第47界IMO预选题) 已知x∈(0,1),令y∈(0,1),且y的小数点后第n位数字是x的小数点后第2位数字.证明:若x为有理数,则y也为有理数.

证 设x=0.x1x2…xn…,

n

≡b(mod3),c2011≡c(mod3),

1018n≡1(mod19),

y=0.y1y2…yn…,

则对于n=1,2,…,有yn=x2n.因为x为有理数,所以数列{xn}从某项开始为周期数列,为了说话方便,不妨设{xn}为周期数列,d为它的一个周期,d=20v,其中n0为非负整

n

数,v为大于1的奇数(这是可以办到的,因为若T为数列的周期,则3T也为周期).现令

ω=?(v),由欧拉定理知,2ω=2?(v)≡1(modv),从而有

2

ω+n0

≡2n0

(movd?(

n0

2,)) 2ω+n0≡2n0(modd), 即

ω+n0

n00

?2n-n≡2n2-

0n

所以对于任意的正整数n>n0,有 2即 2

ω+n

n

≡2

(mdod, )

(modd. )

∵ d是{xn}的周期,从而有 x2ω+n=x2n, 即yn+ω=yn.

综上知,对于任意的n>n0,都有yn+ω=yn,所以{yn}从第n0+1项开始为周期数列,因此y为有理数.

例5

设x=(5+1000

,求[x]的末三位数. 解

令y=(5-1000

.

0<(5-1000

<1,∴ 0<y<1. 又因为

x+y=(5+1000

+(5-1000

=2(51000+C2

10002?5998?(23?3)+C10004

?5996?(23?3)+…+C998

231000?5?(2?3)449+(23?3)500)所以 [x]=x+y-1. 由(1)式知

x+y≡2?5100+0

2?(2?33)500

(mod1 0 0 0 ) ∵ 1000=53

?8,

51000≡0(mod53) (3)

51000=(25)500≡1500=1(mod8) (4)

由(3)得 5

1000

=53t,代入(4)得

53t≡1(mod8),

即 5t≡1(mod,

8 )∴ t≡5(mod8). t≡8k+5,所以 51000

=53t=53(8k+5)≡625(mod1000),

∴ 2?5

1000

≡2?625≡250(mod1000).

又∵ ?(125)=125(1-1)=100,由欧拉定理知 (23?3)100

5

≡1(mod125),∴ (23

?3)

500

≡1(mod125) (5)

1)

2)

( (

数学数论篇三:小学数学数论问题

小升初数论问题

概念:几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做最小公倍数。

从分解质因数中我们可以发现:两个数(或多个数)的公倍数必须具备: ①公倍数必须包含这几个数中所有的质因数,而根据这几个数质因数的关系,我们将这些质因数分为三类,一类是公有的质因数,一类是独有的质因数,一类是大家都没有的(如果大家都没有的个数为0,那么这时的公倍数就是最小公倍数)。

②而最小公倍数又必须同时满足:每组公有的质因数只取一个,这几个数独有的质因数要全部取完,除此之外,不得含有其它的质因数,将这些取出的质因数全部乘起来所得的积就是这几个数的最小公倍数。

精典例题

例1:三个连续的自然数的最小公倍数是168,那么这三个自然数的和等于多少?(1998年小学数学奥林匹克初赛试题)

思路点拨:想一想:三个数的最小公倍数与这三个数有什么关系?友情提示:从分解质因数的角度来思考!

模仿练习:三个连续的自然数的最小公倍数是9828,这三个自然数的和等于多少?(1998年小学数学奥林匹克初赛试题)

例2:有一个数在700到800之间,用15、18和24去除,都不能整除。如果在

这个数上加1,就能同时被15、18和24整除,这个数是多多少?

思路点拨:想一想:如果在这个数加1,就能被15、18、24整除说明这个数加1所得到的数一定是这三个数的……

模仿练习:一个四位数,千位上的数字和百位上的数字都被擦掉了,只知道十位上数字是1,个位上数字是2.如果这个数减去7就能被7整除,减去8就能被8整除,减去9就能被9整除,那么这个四位数是多少?(北京市第二届“迎春杯”刊赛试题)

例3:甲数是36,甲、乙两数的最小公倍数是288,最大公约数是4,乙数应该是多少?

思路点拨:想一想:两个数的最大公约数与它们的最小公倍数以及这两个数之间有什么关系?

模仿练习:甲数是60,甲乙两数的最小公倍数是180,最大公约数是30,乙数应该是多少?

1、有5000多根牙签,可按六种规格分成小包。如果10根一包,那么最后还剩9根。如果9根一包,那么最后还剩8根。第三、四、五、六种的规格是,分别以8、7、6、5根为一包,那么最后也分别剩7、6、5、4根。原来一共有牙签多少根?(北京市第十届“迎春杯”决赛试题)

2、动物园的饲养员给三个群猴子分花生。如只分给第一群,则每只猴子可得12粒;如只分给第二群,则每只猴子可得15粒;如只分给第三群,则每只猴子可得20粒。那么平均分给三群猴子,每只可得多少粒?(北京市第八届“迎春杯”决赛试题)

3、2013个同学排成一列,从排头向排尾1至3报数;再从排尾向排头1至4报数,那么两次报数中都报1的人共有多少人?

4、甲、乙两数的最小公倍数是90,乙、丙两数的最小公倍数是105,甲、丙两数的最小公倍数是126,那么甲数是多少?(1995年小学数学奥林匹克决赛B卷试题)

1.从运动场一端到另一端全长96米,从一端到另一端每隔4米插一面小红

旗,现在要改成每隔6米插一面小红旗,问可以不拔出来的小红旗有多少面?(第一届《小数报》数学竞赛试题)

2.一个自然数被5、6、7整除时余数都是1,在10000以内,这样的数共有多少个?(北京市第一届“迎春杯”刊赛试题)

3.两个数的和是112,最大公约数是16,这两个数是多少?(2010年成都嘉祥外国语学校奖学金考试题)

4.甲从A地往B地,乙、丙两人从B地往A地,三人同时出发,甲首先在途中与乙相遇,之后8分钟又与丙相遇,甲每分钟走70米,乙每分钟走60米,丙每分钟走50米,问:A、B两地相距多少米?

相关热词搜索:数论 数学 初中数学数论 五年级数学数论

相关文章
最新文章

Copyright © 2008 - 2017 版权所有 博文学习网

工业和信息化部 湘ICP备09005888号-2