初等数论基础：容斥原理与欧拉函数

设S是有限集合.按照惯例，用表示S中含元素的个数.若A是集合S的子集，用表示A在S中的补集，即=｛x|x∈S，x∉A｝.此时，显然有进一步，若A1，A2是S的子集，则有

将上述事实再进一步推广，就得到重要的“容斥原理”.

定理2.4.1（容斥原理）　设S是有限集合，P1，P2，…，Pm是m个性质.设Ai是S中具有性质Pi（也可能同时具有其他性质）的元素构成的集合，i=1，2，…，m.则S中不具有性质P1，P2，…，Pm中任何一个性质的元素构成的集合为进一步，有

这里第一个求和号是对所有｛1，2，…，m｝求和，第二个求和号是对所有

求和，第三个求和号是对所有

求和.其余求和号的含义可依次类推.

说明　在证明定理之前，先对这个定理做些说明.当m=2时，有

这个等式右边有4项.当m=3时，有

这个等式右边有8项.在一般情况下，等式（2.4.1）右边的项数是

证明　等式（2.4.1）的左边是S中不具有性质P1，P2，…，Pm中任何一个性质的元素的个数.要证该等式成立，只需证明一个不具有性质P1，P2，…，Pm中任何一个性质的元素对（2.4.1）右边贡献的数值是1，而至少具有性质P1，P2，…，Pm中一个性质的元素对（2.4.1）右边贡献的数值是0.

设x∈S不具有性质P1，P2，…，Pm中的任何一个性质.则x不在任何Ai中，i=1，2，…，m.于是，x对（2.4.1）右边贡献的数值为1-0+0-0+…+（-1）m×0=1.这表明不具有性质P1，P2，…，Pm中任何一个性质的元素对（2.4.1）右边贡献的数值是1.

设y∈S恰好具有性质P1，P2，…，Pm中的n（1≤n≤m）个性质.由于y∈S，故y对|S|的贡献是；y恰好具有n个性质，因而y是A1，A2，…，Am中的某n个集合中的元素，故y对∑|Ai|的贡献是；因为在n个性质中任取两个性质的方法有个，故y是个集合Ai∩Aj中的元素，从而y对∑|Ai∩Aj|的贡献为.依次类推下去，可得y对（2.4.1）右边贡献的数值为注意到当n＜k时有故y对（2.4.1）右边贡献的数值为

这表明至少具有性质P1，P2，…，Pm中之一的元素对等式（2.4.1）右边贡献的数值是0.证毕.

下面介绍数论中重要的欧拉函数，并用容斥原理获得欧拉函数的表达式.

定义2.4.2　设a是正整数，用φ（a）表示序列0，1，2，…，a-1中与a互素的数的个数.这个定义在正整数集上的函数φ称为欧拉函数.前几个正整数的欧拉函数值如下：

容易看出，φ（a）也是序列1，2，…，a-1，a中与a互素的数的个数.

定理2.4.3　设大于1的整数a的标准分解式为则

证明　用Ai表示从1到a中能被pi整除的数的集合，i=1，2，…，n.对任意整数m，容易验证（a，m）≠1当且仅当m可被某个pi整除.于是，φ（a）就是从1到a中不属于任何一个Ai的整数的个数.由容斥原理知(www.xing528.com)

据命题2.1.4，在1到a这a个数中，能被pi整除的数的个数为；由（pi，pj）=1（i≠j）知pi|a，pj|a当且仅当pipj|a.故能被pi，pj同时整除的数的个数为　依次类推，能被p1，p2，…，pn整除的数的个数为　故

推论2.4.4　若p是素数，α是正整数，则φ（pα）=pα-pα-1.特别的，φ（p）=p-1.

推论2.4.5　欧拉函数是积性函数.

证明　显然，φ（1）=1.设a，b是互素的正整数.若a=1或b=1，则有φ（ab）=φ（a）φ（b）.下设分别是a，b的标准分解式.由于a，b互素，故ab的标准分解式为

据定理2.4.3立得φ（ab）=φ（a）φ（b）.这表明φ是积性函数.证毕.

推论2.4.6　设a是大于1的整数且其标准分解式为，则

证明　据推论2.4.5知φ是积性函数.在定理2.2.5中令f=φ，则据推论2.4.4知

推论2.4.7　设a，b∈Z，a＞0，b＞0，则

证明　首先，对任意素数p，有p|a，p|b当且仅当p|（a，b），和p|ab当且仅当p|a或p|b.据定理2.4.3，有

例2.4.8　求不超过360且与360互素的正整数的个数.

解　注意到360=23×32×5，有

故不超过360且与360互素的正整数有96个.解毕.

例2.4.9　利用欧拉函数证明素数有无穷个.

证明　设所有不同的素数为2，3，…，p并记a=2×3×…×p.设c∈｛1，2，…，a｝.若c＞1，则必有素数q使得q|c.但a是所有素数之积，故也有q|a.这表明c与a不互素.于是1，2，…，a中与a互素的仅有1，从而φ（a）=1.另一方面，据定理2.4.3，

φ（a）=20×30×…×p0×（2-1）×（3-1）×…×（p-1）＞1，

矛盾.证毕.