初等数论（四）--几个著名的数论定理
一些常用概念
?欧拉函数?(n)--介于1和n之间与n互质的自然数个数
?缩系---在?(n)个剩余类中各取一个元素，它们形成一个模n的缩系
问题：为什么要介绍缩系这个概念呢？这是因为当我们定一个缩系后，剩余类中的其它元素均可以由缩系生成。设(a,m)?1，则有s,t使得
as?mt?1。
任取一个不是缩系中的元素b，就有
b?asb?mtb
从而有
b?asb(modm)。
即，b可以表成ka(modm)的形式（即，由a的若干倍生成），从而凡是与b有关的数论问题（在模m的意义下可以转化为a的问题）。这就是群论中的生成元的问题。在高中里面的复数理论中也是如此。
下面这个结果表明了一种构造缩系的方法：
例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。所以
?(pa)?pa?pa?1?pa?1??。
p??如果自然数n?p11p22...pkk,那么
????1??(n)?n?1????1??1?1??1??...?1??? ???p1??p2?pk??关于?(n)还有其他表达方式：
?(n)?n??1??。
ppnp质数??1??注意：大家可以尝试用容斥原理来证明这个公式。
下面介绍著名的费马小定理
例2.设m是一个自然数，(a,m)=1。证明：a?(m)?1(modm)。这就是著名的欧拉定理。
如果取m?p为质数，那么就成为了费马小定理。 证明：设x1,x2,...,xt(t=?(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???l1?2a...a(l?p?1)的项。在(ai1?ai2?...?aip)p?1展开后得到形如ai?ii12l?中含有
?lp?l1?2的项有ai?a...a(l?p?1)Cii2p?1?l个（即，从ai1,ai2,...,aip以外的书中取p?l个与它搭12l配成形如ai,ai,...,ai的组合）。注意到C2p?l?1?12pp?l(2p?1?l)(2p?l)...(p?1)p被p整除，
(p?l)!因此上面和式左边?0(modp)。矛盾表明结论成立！
初等数论（四）-几个著名的数论定理
