《初等数论几个著名的数论定理.docx》由会员分享，可在线阅读，更多相关《初等数论几个著名的数论定理.docx（5页珍藏版）》请在三一办公上搜索。
1、初等数论几个著名的数论定理初等数论-几个著名的数论定理 一些常用概念 欧拉函数j(n)-介于1和n之间与n互质的自然数个数 缩系-在j(n)个剩余类中各取一个元素，它们形成一个模n的缩系 问题：为什么要介绍缩系这个概念呢？这是因为当我们定一个缩系后，剩余类中的其它元素均可以由缩系生成。设(a,m)=1，则有s,t使得 as+mt=1。 任取一个不是缩系中的元素b，就有 b=asb+mtb 从而有 basb(modm)。 即，b可以表成ka(modm)的形式，从而凡是与b有关的数论问题。这就是群论中的生成元的问题。在高中里面的复数理论中也是如此。 下面这个结果表明了一种构造缩系的方法： 例1.
2、设(m,n)=1。如果a1,a2,.,at,b1,b2,.,bs分别是模m和模n的缩系，那么 S=mbi+naj1is,1jt 就是模mn的缩系。 解答：第一步。先证明S中每一个元素都与mn互质。这是显然的。 第二步。证明S任意两个数关于模mn不同余。假定有某两个数mbi+naj与mbi+naj关于模mn同余， mbi+najmbi+naj(modmn) 则必有m(bi-bi)n(aj-aj)(modmn)。从而有 (bi-bi)0(modn),(ai-ai)0(modm)， 即有bi=bi,aj=aj，矛盾！ 第三步。证明：如果一个数c与mn互质，那么必然与S中某个元素关于模mn同余。 由于
3、(m,n)=1,方程mxc(modn)在模n剩余类中有解；由于(c,n)=1,所以(x,n)=1。因此，x与某个bi在模n的同一个剩余类中，即有 mbic(modn); 同理有aj使得 najc(modm) 自然有 mbi+najc(modn);mbi+najc(modm).根据(m,n)=1, mbi+najc(modmn) 这就网完成了证明。 例2.在1,2,3,.,pa中有多少个数与pa互质？ 解答:在1,2,3,.,pa中不与pa互质的数有形式kp,1kpa-1。所以 j(pa)=pa-pa-1=pa1-。 p如果自然数n=p11p22.pkk,那么 aaa1j(n)=n1-1111-
4、.1- p1p2pk关于j(n)还有其他表达方式： j(n)=n1-。 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.axtx1x2.xt(modm)。 证明完毕。
5、 例3.证明：任意的2p-1个整数中一定可以选出p个数，它们的和可以被p整除，这里p是一个质数。 证明：反证法。如果a1,a2,.,a2p-1中任意p个数ai,ai,.,ai的和都不是p的倍数，那么12p由费马小定理有 (ai1+ai2+.+aip)p-11(modp)。 注意到形如上式的组合共有C2p-1个，对所有这样可能的组合求和后得到; p因为C2pp-1(ai1+ai2+.+aip)p-1C2pp-1(modp) 2p-1=1(modp)。 pal1a2a.a(lp-1)的项。在(ai1+ai2+.+aip)p-1展开后得到形如aiaii12l中含有alp-l1a2的项有aiaa.a(lp-1)Cii2p-1-l个。注意到C2p-l-1=12pp-l(2p-1-l)(2p-l).(p+1)p被p整除，(p-l)!因此上面和式左边0(modp)。矛盾表明结论成立！
