初等数论几个著名的数论定理.docx

初等数论几个著名的数论定理初等数论-几个著名的数论定理 一些常用概念 ·欧拉函数j(n)-介于1和n之间与n互质的自然数个数 ·缩系-在j(n)个剩余类中各取一个元素，它们形成一个模n的缩系 问题：为什么要介绍缩系这个概念呢？这是因为当我们定一个缩系后，剩余类中的其它元素均可以由缩系生成。设(a,m)=1，则有s,t使得 as+mt=1。 任取一个不是缩系中的元素b，就有 b=asb+mtb 从而有 bºasb(modm)。 即，b可以表成ka(modm)的形式，从而凡是与b有关的数论问题。这就是群论中的生成元的问题。在高中里面的复数理论中也是如此。 下面这个结果表明了一种构造缩系的方法： 例1. 设(m,n)=1。如果a1,a2,.,at,b1,b2,.,bs分别是模m和模n的缩系，那么 S=mbi+naj1£i£s,1£j£t 就是模mn的缩系。 解答：第一步。先证明S中每一个元素都与mn互质。这是显然的。 第二步。证明S任意两个数关于模mn不同余。假定有某两个数mbi+naj与mbi+naj关于模mn同余， ''mbi+najºmbi'+na'j(modmn) 则必有m(bi-bi)ºn(aj-aj)(modmn)。从而有 ''(bi-bi')º0(modn),(ai-ai')º0(modm)， 即有bi=bi,aj=aj，矛盾！ 第三步。证明：如果一个数c与mn互质，那么必然与S中某个元素关于模mn同余。 由于(m,n)=1,方程mxºc(modn)在模n剩余类中有解；由于(c,n)=1,所以(x,n)=1。因此，x与某个bi在模n的同一个剩余类中，即有 ''mbiºc(modn); 同理有aj使得 najºc(modm) 自然有 mbi+najºc(modn);mbi+najºc(modm).根据(m,n)=1, mbi+najºc(modmn) 这就网完成了证明。 例2.在1,2,3,.,pa中有多少个数与pa互质？ 解答:在1,2,3,.,pa中不与pa互质的数有形式kp,1£k£pa-1。所以 j(pa)=pa-pa-1=paç1-÷。 pèø如果自然数n=p11p22.pkk,那么 aaaæ1öj(n)=nç1-èææ1öæ1ö1ö´1-´.´1-ç÷ ÷ç÷p1øèp2øpkøè关于j(n)还有其他表达方式： j(n)=nÕç1-÷。 ppnp质数æè1öø注意：大家可以尝试用容斥原理来证明这个公式。 下面介绍著名的费马小定理 例2.设m是一个自然数，(a,m)=1。证明：aj(m)º1(modm)。这就是著名的欧拉定理。如果取m=p为质数，那么就成为了费马小定理。 证明：设x1,x2,.,xt(t=j(m)是一个模m的缩系。那么 ax1,ax2,.,axt 中任何两个都与m互质，其中没有两个相同。从而它也是一个缩系，在模m的意义下，ax1,ax2,.,axt仅仅是x1,x2,.,xt的一个置换。从而有 ax1ax2.axtºx1x2.xt(modm)。 证明完毕。 例3.证明：任意的2p-1个整数中一定可以选出p个数，它们的和可以被p整除，这里p是一个质数。 证明：反证法。如果a1,a2,.,a2p-1中任意p个数ai,ai,.,ai的和都不是p的倍数，那么12p由费马小定理有 (ai1+ai2+.+aip)p-1º1(modp)。 注意到形如上式的组合共有C2p-1个，对所有这样可能的组合求和后得到; på因为C2pp-1ºê(ai1+ai2+.+aip)p-1ºC2pp-1(modp) é2p-1ùú=1(modp)。 pëûal1a2a.a(l£p-1)的项。在(ai1+ai2+.+aip)p-1展开后得到形如aiaii12lå中含有alp-l1a2的项有aiaa.a(l£p-1)Cii2p-1-l个。注意到C2p-l-1=12pp-l(2p-1-l)(2p-l).(p+1)p被p整除，(p-l)!因此上面和式左边º0(modp)。矛盾表明结论成立！