定义
φ(n) 表示 1∼n 中与 n 互质的正整数个数,即
φ(n)=1⩽k⩽ngcd(k,n)=1∑1.
约定 φ(1)=1。
基本性质
(a) 素数
若 p 是素数,则
φ(p)=p−1.
因为 1∼p 中除了 p 自身,其余 p−1 个数都与 p 互质。
(b) 素数幂
若 p 是素数,则
φ(pk)=pk−pk−1=pk(1−p1).
因为 1∼pk 中与 pk 不互质的数恰好是 p 的倍数,共有 pk−1 个。
计算公式
设 n=p1α1p2α2⋯prαr 为标准分解,则
φ(n)=ni=1∏r(1−pi1).
证明(容斥原理):在 1∼n 中,先去掉所有 p1 的倍数,再去掉所有 p2 的倍数,再把被重复去掉的 p1p2 的倍数加回来。依此类推,得到
φ(n)=n−i∑pin+i<j∑pipjn−i<j<k∑pipjpkn+⋯=n(1−i∑pi1+i<j∑pipj1−⋯)=ni=1∏r(1−pi1).
最后一步用了展开式 ∏i(1−xi)=1−∑ixi+∑i<jxixj−⋯。
定理 1
对任意 n⩾1,有
d∣n∑φ(d)=n.
思路
考虑集合
S={ni1⩽i⩽n},
则 ∣S∣=n。对每个 d∣n,令
Sd={di1⩽i⩽d, gcd(i,d)=1},
则 ∣Sd∣=φ(d)。只需证明 {Sd}d∣n 构成 S 的一个划分。
证明
(1)两两不交。 设 d,d′∣n 且 d=d′。若存在 a∈Sd∩Sd′,则
a=di=d′i′,1⩽i⩽d, 1⩽i′⩽d′,
且 gcd(i,d)=gcd(i′,d′)=1。由 id′=i′d 得 d∣id′;又因为 gcd(i,d)=1,所以 d∣d′。同理 d′∣d,于是 d=d′,矛盾。因此 Sd∩Sd′=∅。
(2)并集包含于 S。 任取 a∈⋃d∣nSd,存在 d∣n 使 a=i/d,其中 1⩽i⩽d 且 gcd(i,d)=1。由 d∣n,
a=di=ni⋅(n/d),
且 1⩽i⋅(n/d)⩽n,故 a∈S。
(3)S 包含于并集。 任取 a∈S,写 a=i/n,其中 1⩽i⩽n。令 d=gcd(i,n),则
a=n/di/d,1⩽di⩽dn,gcd(di,dn)=1,
故 a∈Sn/d。因此 S⊂⋃d∣nSd。
综上,S=⨆d∣nSd,于是
d∣n∑φ(d)=∣S∣=n.□
引理
设 gcd(m,n)=1。若 t1 遍历 n 的全部因子,t2 遍历 m 的全部因子,则 t1t2 遍历 mn 的全部因子。
证明
第一步:t1t2∣mn。 由 t1∣m、t2∣n,立即得到 t1t2∣mn。
第二步:表示唯一。 证明 t1t2=t1′t2′ 当且仅当 t1=t1′、t2=t2′。
假设 t1t2=t1′t2′ 且 (t1,t2)=(t1′,t2′)。由
t1∣t1′t2′,t1′∣t1t2
以及 gcd(m,n)=1,可得 gcd(t1,t2′)=1。于是 t1∣t1′;同理 t1′∣t1,故 t1=t1′,进而 t2=t2′,与假设矛盾。
第三步:遍历全部因子。 任取 t∣mn,令
t1=gcd(t,m),t2=t1t.
则 t1∣m。又
gcd(gcd(t,m)t,gcd(t,m)m)=1,
且 t/t1∣n,所以 t2∣n。因此每个 t∣mn 都能写成 t1t2 的形式。
结合三步,引理得证。□
积性(定理 2)
若 gcd(m,n)=1,则
φ(mn)=φ(m)φ(n).
法一:直接展开
设 m=∏ipiαi,n=∏jqjβj。由 gcd(m,n)=1 知 {pi} 与 {qj} 不相交。于是
φ(mn)=mnp∣mn∏(1−p1)=mnpi∣m∏(1−pi1)qj∣n∏(1−qj1)=mpi∣m∏(1−pi1)⋅nqj∣n∏(1−qj1)=φ(m)φ(n).□
法二:数学归纳
当 m=n=1 时结论显然。假设结论对所有小于 mn 的正整数成立。由定理 1,
mn=t1∣m∑φ(t1)t2∣n∑φ(t2)=t1∣m∑t2∣n∑φ(t1)φ(t2).
因为 gcd(m,n)=1,所以 gcd(t1,t2)=1,从而 φ(t1)φ(t2)=φ(t1t2)。于是
mn=t1∣m, t2∣n(t1,t2)=(m,n)∑φ(t1t2)+φ(m)φ(n)=t1∣m, t2∣n∑φ(t1t2)−φ(mn)+φ(m)φ(n)=t1t2∣mn∑φ(t1t2)−φ(mn)+φ(m)φ(n)=mn−φ(mn)+φ(m)φ(n),
最后一步再次使用定理 1。因此 φ(mn)=φ(m)φ(n)。□
推论:由积性,
φ(n)=i=1∏rφ(piαi)=i=1∏rpiαi−1(pi−1).
定理 3
设 gcd(m,n)=d,则
φ(mn)=φ(m)φ(n)φ(d)d.
若 a∣b,则 φ(a)∣φ(b)。
证明
(1) 令 gcd(m,n)=d。则
φ(mn)=mnp∣mn∏(1−p1)=mn⋅p∣d∏(1−p1)p∣m∏(1−p1)p∣n∏(1−p1)=d⋅p∣d∏(1−p1)mp∣m∏(1−p1)⋅np∣n∏(1−p1)⋅d=φ(m)φ(n)φ(d)d.□
(2) 设 b=ac,并令 d=gcd(a,c)。由(1),
φ(b)=φ(ac)=φ(a)φ(c)φ(d)d=φ(a)⋅p∣d∏(1−p1)cp∣c∏(1−p1)=φ(a)⋅cp∣cp∤d∏(1−p1).
其中最后一步约去了 p∣d 的因子。将 c 按素因子拆开:
cp∣cp∤d∏(1−p1)=p∣cp∣d∏pvp(c)⋅p∣cp∤d∏(pvp(c)−pvp(c)−1).
右边是整数,故 φ(a)∣φ(b)。□