数论的几个重要定理精选.docx
- 文档编号:16994664
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:11
- 大小:72.46KB
数论的几个重要定理精选.docx
《数论的几个重要定理精选.docx》由会员分享,可在线阅读,更多相关《数论的几个重要定理精选.docx(11页珍藏版)》请在冰点文库上搜索。
数论的几个重要定理精选
11数论的几个重要定理
欧拉定理、费马小定理、威尔逊定理及中国剩余定理是数论的四大定理,它们是解决数论问题的重要工具。
下面介绍这几个定理在竞赛数学中的应用方法。
1.基本原理
定理1(欧拉定理)设m为大于1的整数,(a,m)1,(m)为欧拉函数,则
a(m)1(modm).
证设ri,r2,…,r(m)为模m的一个简化剩余系,因为(a,m)1,所以
ar1,ar2,…,ar(m)也是模m的一个简化剩余系,从而有
(arja)…(ar⑴))也…r⑴)(modm),
即a(m)(rr2…r(m))「厂…r⑴)(modm)
(1)
因为(盹…r(m),m)1,所以由
(1)得a(m)1(modm).
定理2(费马小定理)设p是素数,(a,p)1,则
ap11(modp).
证因为p是素数,所以(p)p1,由欧拉定理知
a(p)1(modp),
ap11(modp).
推论设p为素数,a为整数,则
apa(modp)
(2)
证当pa时,
(2)式显然成立.当p不能整除a时,因为p为素数,所以(a,p)1.
由定理2得ap11(modp),
apa(modp).
定理3(威尔逊定理)若p为素数,则
(p1)!
1(modp).
证a2,3,-,p2,因为(a,p)1,所以a,2a,…,(p1)a也是模p的简化
剩余系,故存在唯一的b1,2,…,p1,使得
ba1
(modp)
(1)
•••a2,3,
…,p2,•b
1,bp1.若ba,贝U
a21(modp)
•••(a1)(a
1)0(modp).
•••a1或
1(modp),
这与a2,3,…,
p2矛盾.综上即知b2,3,-,p2且ba
将2,3,…,p
2中的数按
(1)
式两两配对,得
234
…(p2)1(modp),
•(p1)!
1(modp).
定理4(中国剩余定理)设mi,m2,…,mk是k个两两互质的正整数,mmg?
…mk,
Mi—,i1,2,…,k,则同余式组mi
xa1(modmj
(1)
xa2(modmt)xak(modmk)
有唯一解
其中MiMi1(modm),i1,2,…,k.
证容易验证
(2)是
(1)的解.又若x,x均是
(1)的解,则对于i1,2,…,k,有
xa(modmi)
xa(modmi),
从而有
xx0(modmi),又因为m^m?
…,mk两两互质,从而有
xx(modm),
所以X与X是同余式组
(1)的相同解•
设m1,(a,m)1,则由欧拉定理知a(m)1(modm),我们把满足条件
r
a1(modm)
的最小正整数r称为a对模m的阶,或称为a对模m的指数.关于a对模m的阶,我们有如下结论•
定理5设m1,(a,m)1,a对模m的阶为n0,n为正整数若an1(modm),则n0n.
证由带余除法知,存在非负整数q及r,使得
nqnor,0rn°.
所以1anaqn0r(an0)qarar(modm),
由于rn0,由n0的最小性知r0,所以n0n.
2.方法解读
用上述定理解题,除应掌握数论解题的基本方法外,还应对这几个定理的用途有一定的认识.一般说来,欧拉定理与费马小定理提供了降幕与归1的工具.威尔逊定理提供了处理连
续整数的积的方法.中国剩余定理提供了某些存在性问题的构造方法.定理5提供了由方幕的
指数导出整除关系的途径.
例1求使2n1为7的倍数的所有正整数n.
解T212(mod7),224(mod7),231(mod7),
所以2对模7的阶为3.又因为2n1(mod7),所以由定理5知3n,即n3k(kN).
例2设整数a,b,c满足abc0,记da2011b2011c2011,求证|d不是素数.
证ta2a(mod2),
201120112011
二aa(mod2)同理知bb(mod2),cc(mod2),
…abcabc0(mod2),
•••2d.
・2011a
2010
aa
/3\670
(a)a
a670a
a669a2a3223a2
2232
aa
a224aa78aa26
a
a27a9a3a(mod3),
同理可证
.2011
b
b(mod3),
2011c
c
(mod3),
.2011
.2011
2011.
c0
a
b
cab
(mod3),
•••3d.又:
(2,3)1,•••6d,所以d不是素数•
例3证明:
数列1,19,119,1119,11119,…中有无穷多个合数.
证因为19是素数,(10,19)1,由费马小定理知10181(mod19),所以对于任
意的正整数n,有
1018n1(mod19),
18n
1010(mod19),
911…10(mod19),
18n个1
(19,9)1,
•19
11…1,•
19
11…1
19,即19
11…119
18n个1
18n个1
18n个1
由于正整数n有无穷多个,所以数列中有无穷多项被19整除,故数列中有无穷多项为合数
例4(第47界IMO预选题)已知x(0,1),令y(0,1),且y的小数点后第n位数
字是X的小数点后第2n位数字.证明:
若X为有理数,则y也为有理数.
证设X0.X/2…Xn…,
yO.yv2…yn…,
则对于n1,2,…,有ynX2n.因为X为有理数,所以数列Xn从某项开始为周期数列,
为了说话方便,不妨设Xn为周期数列,d为它的一个周期,d2n°v,其中n°为非负整
数,v为大于1的奇数(这是可以办到的,因为若T为数列的周期,则3T也为周期).现令
(v),由欧拉定理知,22(v)1(modv),从而有
2n02n0(mod(v2n0)),即2n2n0(modd),
所以对于任意的正整数nn0,有2n02nn02n02nn0(modd),
d是Xn的周期,从而有x2nx2n,即ynyn.
综上知,对于任意的nno,都有ynyn,所以y从第n。
1项开始为周期数列,因此y为有理数.
例5设x(52.6)1000,求x的末三位数
由(3)得5100053t,代入(4)得
解令y(52、、6)1000.
•••0(52•一6)10001
0y1.
又因为xy(52、.6)1000
(5
2®000
〜l10002,98
—3
…4,96_3—2
2(5C10005
(2
3)C10005(23)
53t1(mod8),
即5t1(mod8),
•••t5(mod8).
8k5,所以51000
33
5t5(8k5)625(mod1000),
•-2510002625250(mod1000).
13100
又•••(125)=125(1-—)=100,由欧拉定理知(23)1(mod125),
5
•-(233)5001(mod125)(5)
又(233)5000(mod8)(6)
由(5)得(233)500125t1,代入(6)得
125t10(mod8),
即5t10(mod8),
•••t3(mod8).
二t8k3,代入得(233)500125(8k3)1376(mod1000),
•-2(233)5002376752(mod1000).
综上知,xy2510002(233)5002507522(mod1000),所以xy11(mod1000),故x的末三位数为001.
例6求具有如下性质的素数p的最大值:
存在1,2,…,p的两个排列(这两个排列可
以相同)a「a2,…,ap与db,…,bp,使得印^赴匕?
,…,apbp被p除所得的余数互不相同.
解不妨设印1,a22,…,app.若bpp,则存在i1,2,…,p1,使得
bip,从而有aibi0(modp),apbp0(modp),从而有abapbp(modp),
这与题设矛盾,因此有bpp.
因为apbp0(modp),又玄初^匕?
…,apbp被p除所得的余数互不相同,所以a1b1,a2b2,^,ap1bp1被p除的余数构成的集合为1,2,…,p1,由有威尔逊定理,得
的唱①)…(apgJ123…(p1)(p1)!
1(modp).
又(a1b!
)(a2b2)…(ap初卩J佝玄2…ap"(匕叔…bpJ
(p1)!
(p1)!
(1)
(1)1(modp),
11(modp),•20(modp),•p2.
由于p为素数,所以p2.容易验证p2满足要求.故所求的最大值为2.
例7设整数n,q满足n5,2qn且q不为某个质数的平方,试证:
这里x表示x的这个数部分
证若q为合数,因为q不为质数的平方,所以存在大于1的整数a,b,ab,使
得qab.因为qn,所以an1,bn1,从而有q(n1)!
,因此
(n1)!
(n1)!
•-(q1)(n1)!
q(n1)!
(q1,q)1,
•••(q1)q(n1)!
(q1)(n1)!
(n1)!
,故结论成立.
若q为质数,当qn,易知q(n1)!
从而有
(n1)!
(n1)!
又因为(q1)(n1)!
(q1,q)1,所以(q1)q(n1)!
...g1)g,,结论成立.
当qn时,因为q为质数,由威尔逊定理知(n1)!
(q1)!
1(modq),所以
(n
1)!
1
0
(modq),
•q
(n1)!
1,
所以
(n1)!
(n
1)!
11
(n
1)!
(q1)
q
q
q
又因为
(q
1)
(n1)!
(q
1),(q
1,q)
1,所以(q1)q
(n1)!
(q1),
•(q
1)
(n
1)!
(q
1)
(n1)!
,故?
结论成立.
例8若一个正整数的标准分解式中,每个素约数的幕次都大于1,则称这个数为幕数
证明:
对于任意的正整数n(n2),存在n个连续的正整数,其中每一个数都不是幕数.
证选取n个互不相同的素数山,卩2,…,pn.由中国剩余定理知,同余式组
xp(modp12)
x1p2(modp2)
2
x(n1)Pn(modpn)
222
0,1,2,…,n1,
个连续正整数
有解.设xXo(modPiP2…Pn)(x00)是
(1)的唯一解,则对于
有Pi2不整除xoi且Pixoi,故X。
i不是幕数.因此,
Xo,Xo
1,xo2,…,xo(n1)满足要求.
9设n1,n2n1,证明3n.
设p是n的最小素因子,2对模p的阶为r.
(1)
22n1(modp)
又因为
p为奇素数,所以(2,p)1.由费马小定理知
习题11
1.已知x17,当n1时,Xn7xn1,求xn的末两位数
2•证明数列
37,337,3337,33337,
中有无穷多个合数.
3.证明有无穷多个正整数n,使得1oo
(2nn2).
最新文件
改
仅供参考已改成word文本
方便更
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数论 几个 重要 定理 精选