欧拉函数的一些性质以及证明

· · 个人记录

性质1

    若p为质数，则φ（p）=p-1；
证明：因为p为质数，所以p以内的数均与p互质。

性质2

    若p为质数，且a为正整数，则φ（p^a）=p^a-p^(a-1);
证明：令n=p^a。因为p为质数，于是n内与n不互质的数为p的倍数.设为ap,易
得1≤a＜p^(k-1)，也就是说n内与p不互质的数有p^(a-1)-1个。于是n内与n互
质的数有n-1-p^（a-1）-1个即φ（p^a）=p^a-p^(a-1)。

性质3（可积性）

    若n与m互质，则φ（m*n）=φ（m）*φ（n）；
证明：考虑构造如下n*m的矩阵：
1       2   ……  r      ……   m
m+1     m+2     m+r     2m
2m+1        2m+2        2m+r        3m
……      ……      ……      ……
(n-1)m+1        (n-1)m+2    (n-1)m+r    nm
在第一行从1-m中显然有φ（m）个数与m互质。设互质的一列第一个数为r，那么
显然km+r也与m互质，所以与m互质的行有φ（m）行。考虑任意一列，若k1*m+r
≡k2*m+r （mod n）可得n∣k1-k2显然不成立，于是我们得到一个模n下的完全
剩余系，在这个完全剩余系里有φ（n）个与n互质的数，因为若x与n互质那么分
数（x+qn）/n一定无法约分，也就是说x在n下的同余类也与n互质，那么φ（m*n）
=φ（m）*φ（n）。

性质4（欧拉函数的计算式）

    设n=∏(pi^ai)（质因数分解）,则φ(n)=n∏（1-1/pi）;
证明:φ（n）=φ（∏(pi^ai)）=∏φ(pi*ai)(可积性)=(p1^a1-p1^(a1-1))*(p2^a2-
p2^(a2-1)*……(pm^am-pm^(am-1))（性质2）=n∏（1-1/pi）(提出pi^ai)。

性质5

    若n为奇数，则φ（2*n）=φ（n）；
证明n为奇数，2与n互质。于是φ（2*n）=φ（2）*φ（n）=φ（n）；

性质6

    设n是一个大于2的正整数，那么∑φ（d）=n，其中d是n的因数;
证明:先设f（x）=Σφ（d），其中d为x的因数。
    首先证明  f（x)为积性函数(对m，n互质的情况下)
    证明：f（n）*f（m）=Σφ（i）*Σφ（j） （i为n的因数，j为m的因数）
              =ΣΣφ（i）*φ（j）
              =Σφ（d） （d是mn的因数）
              =f（n*m）
            所以f（x）为积性函数
设n=∏(pi^ai)（质因数分解），则f（n）=∏f（pi^ai）
而f（p^k）=φ（1）+φ（p）+φ（p^2）+……+φ（p^k）=1+(p-1)+(p^2-p)+……+（p^k
-p^(k-1))=p^k
于是f（n）=∏f（pi^ai）=∏（pi^ai）=n。