Brstjjy

  本文介紹的是小於或等於n的正整數中與n互質的數的數目。關於形式為ϕ(q)=∏k=1∞(1−qk){displaystyle phi (q)=prod _{k=1}^{infty }(1-q^{k})}的函數，請見「歐拉函數 (複變函數)」。

当n为1至1000的整数时φ(n){displaystyle varphi (n)}的值

在數論中，對正整數n，歐拉函數φ(n){displaystyle varphi (n)}是小於或等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數（由高斯所命名）或是歐拉總計函數^[1]（totient function，由西爾維斯特所命名）。

例如φ(8)=4{displaystyle varphi (8)=4}，因為1,3,5,7均和8互質。

欧拉函数实际上是模n的同余类所构成的乘法群（即环Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} }的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起構成了欧拉定理的證明。

歷史：欧拉函數與費馬小定理

1736年，欧拉證明了费马小定理^[2]：

假若 p{displaystyle p} 為質數，a{displaystyle a} 為任意正整數，那麼 ap−a{displaystyle a^{p}-a} 可被 p{displaystyle p} 整除。

然後欧拉予以一般化：

假若 a{displaystyle a} 與 n{displaystyle n} 互質，那麼 aφ(n)−1{displaystyle a^{varphi (n)}-1} 可被 n{displaystyle n} 整除。亦即，aφ(n)≡1(modn){displaystyle a^{varphi (n)}equiv 1{pmod {n}}}。

其中 φ(n){displaystyle varphi (n)} 即為歐拉總計函數。如果 n{displaystyle n} 為質數，那麼 φ(n)=n−1{displaystyle varphi (n)=n-1}，因此，有高斯的版本^[3]：

假若 p{displaystyle p} 為質數，a{displaystyle a} 與 p{displaystyle p} 互質（a{displaystyle a} 不是 p{displaystyle p} 的倍數），那麼 ap−1≡1(modp){displaystyle a^{p-1}equiv 1{pmod {p}}}。

欧拉函數的值

φ(1)=1{displaystyle varphi (1)=1}（小于等于1的正整数中唯一和1互質的數就是1本身）。

若n是質數p的k次冪，φ(n)=φ(pk)=pk−pk−1=(p−1)pk−1{displaystyle varphi (n)=varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}，因為除了p的倍數外，其他數都跟n互質。

歐拉函數是積性函數，即是说若m,n互質，φ(mn)=φ(m)φ(n){displaystyle varphi (mn)=varphi (m)varphi (n)}。證明：設A, B, C是跟m, n, mn互質的數的集，據中國剩餘定理，A×B{displaystyle Atimes B}和C{displaystyle C}可建立雙射(一一對應)的關係。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此φ(n){displaystyle varphi (n)}的值使用算術基本定理便知，

若n=p1k1p2k2⋯prkr{displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}}}

則φ(n)=∏i=1rpiki−1(pi−1)=∏p∣npαp−1(p−1)=n∏p|n(1−1p){displaystyle varphi (n)=prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=prod _{pmid n}p^{alpha _{p}-1}(p-1)=nprod _{p|n}left(1-{frac {1}{p}}right)}。

其中αp{displaystyle alpha _{p}}是使得pα{displaystyle p^{alpha }}整除n{displaystyle n}的最大整数α{displaystyle alpha }（这里αpi=ki{displaystyle alpha _{p_{i}}=k_{i}}）。

例如φ(72)=φ(23×32)=23−1(2−1)×32−1(3−1)=22×1×3×2=24{displaystyle varphi (72)=varphi (2^{3}times 3^{2})=2^{3-1}(2-1)times 3^{2-1}(3-1)=2^{2}times 1times 3times 2=24}

性质

n的欧拉函数φ(n){displaystyle varphi (n)} 也是循环群 C_n 的生成元的个数（也是n阶分圆多项式的次数）。C_n 中每个元素都能生成 C_n 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， C_n 的所有子群都具有 C_d 的形式，其中d整除n（记作d | n）。因此只要考察n的所有因数d，将 C_d 的生成元个数相加，就将得到 C_n 的元素总个数：n。也就是说：

∑d∣nφ(d)=n{displaystyle sum _{dmid n}varphi (d)=n}

其中的d为n的正约数。

运用默比乌斯反转公式来“翻转”这个和，就可以得到另一个关于φ(n){displaystyle varphi (n)}的公式：

φ(n)=∑d∣nd⋅μ(n/d){displaystyle varphi (n)=sum _{dmid n}dcdot mu (n/d)}

其中 μ 是所谓的默比乌斯函数，定义在正整数上。

對任何兩個互質的正整數a, m（即 gcd(a,m) = 1），m≥2{displaystyle mgeq 2}，有

aφ(m)≡1(modm){displaystyle a^{varphi (m)}equiv 1{pmod {m}}}

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出，因为任意与m互质的a都属于环 Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} } 的单位元组成的乘法群Z/nZ×{displaystyle mathbb {Z} /nmathbb {Z} ^{times }}

當m是質數p時，此式則為：

ap−1≡1(modp){displaystyle a^{p-1}equiv 1{pmod {p}}}

即費馬小定理。

生成函数

以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：∑d|nφ(d)=n{displaystyle sum _{d|n}varphi (d)=n}。

由φ{displaystyle varphi }(n)生成的狄利克雷级数是：

∑n=1∞φ(n)ns=ζ(s−1)ζ(s).{displaystyle sum _{n=1}^{infty }{frac {varphi (n)}{n^{s}}}={frac {zeta (s-1)}{zeta (s)}}.}

其中ζ(s)是黎曼ζ函数。推导过程如下：

ζ(s)∑f=1∞φ(f)fs=(∑g=1∞1gs)(∑f=1∞φ(f)fs){displaystyle zeta (s)sum _{f=1}^{infty }{frac {varphi (f)}{f^{s}}}=left(sum _{g=1}^{infty }{frac {1}{g^{s}}}right)left(sum _{f=1}^{infty }{frac {varphi (f)}{f^{s}}}right)}

.               =∑h=1∞(∑fg=h1⋅φ(g))1hs{displaystyle . =sum _{h=1}^{infty }left(sum _{fg=h}1cdot varphi (g)right){frac {1}{h^{s}}}}

.               =∑h=1∞(∑fg=hφ(g))1hs=∑h=1∞(∑d|hφ(d))1hs{displaystyle . =sum _{h=1}^{infty }left(sum _{fg=h}varphi (g)right){frac {1}{h^{s}}}=sum _{h=1}^{infty }left(sum _{d|h}varphi (d)right){frac {1}{h^{s}}}}

使用开始时的等式，就得到：∑h=1∞(∑d|hφ(d))1hs=∑h=1∞hhs{displaystyle sum _{h=1}^{infty }left(sum _{d|h}varphi (d)right){frac {1}{h^{s}}}=sum _{h=1}^{infty }{frac {h}{h^{s}}}}

于是∑h=1∞hhs=ζ(s−1){displaystyle sum _{h=1}^{infty }{frac {h}{h^{s}}}=zeta (s-1)}

欧拉函数生成的朗贝级数如下：

∑n=1∞φ(n)qn1−qn=q(1−q)2{displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}={frac {q}{(1-q)^{2}}}}

其对于满足 |q|<1 的q收敛。

推导如下：

∑n=1∞φ(n)qn1−qn=∑n=1∞φ(n)∑r≥1qrn{displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}=sum _{n=1}^{infty }varphi (n)sum _{rgeq 1}q^{rn}}

后者等价于：

∑k≥1qk∑n|kφ(n)=∑k≥1kqk=q(1−q)2.{displaystyle sum _{kgeq 1}q^{k}sum _{n|k}varphi (n)=sum _{kgeq 1}kq^{k}={frac {q}{(1-q)^{2}}}.}

欧拉函数的走势

随着n变大，估计φ(n){displaystyle varphi (n)} 的值是一件很难的事。当n为质数时，φ(n)=n−1{displaystyle varphi (n)=n-1}，但有时φ(n){displaystyle varphi (n)}又与n差得很远。

在n足够大时，有估计：

对每个 ε > 0，都有n > N(ε)使得 n1−ε<φ(n)<n{displaystyle ,n^{1-varepsilon }<varphi (n)<n}

如果考虑比值：

φ(n)/n,{displaystyle ,varphi (n)/n,}

由以上已经提到的公式，可以得到其值等于类似1−p−1{displaystyle 1-p^{-1}}的项的乘积。因此，使比值小的n将是两两不同的质数的乘积。由素数定理可以知道，常数 ε 可以被替换为：

Clog⁡log⁡n/log⁡n.{displaystyle C,log log n/log n.}

φ{displaystyle varphi }就平均值的意义上来说是与n很相近的，因为：

1n2∑k=1nφ(k)=3π2+O(log⁡nn){displaystyle {frac {1}{n^{2}}}sum _{k=1}^{n}varphi (k)={frac {3}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right)}

其中的O表示大O符号。这个等式也可以说明在集合 {1, 2, ..., n} 中随机选取两个数，则当n趋于无穷大时，它们互质的概率趋于 6/π2{displaystyle 6/pi ^{2}} 。一个相关的结果是比值φ(n)/n{displaystyle varphi (n)/n}的平均值：

1n∑k=1nφ(k)k=6π2+O(log⁡nn).{displaystyle {frac {1}{n}}sum _{k=1}^{n}{frac {varphi (k)}{k}}={frac {6}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right).}

其他与欧拉函数有关的等式

1. φ(nm)=nm−1φ(n){displaystyle ;varphi left(n^{m}right)=n^{m-1}varphi (n)}


2. 
   ∀a∈N,∀n∈N, ∃l∈N{displaystyle forall ain N,forall nin N, exists lin N} 使得 [(a>1∧n>1)→(l|φ(an−1)∧l≥n)]{displaystyle [(a>1land n>1)rightarrow (l|varphi (a^{n}-1)land lgeq n)]}
   


3. 
   ∀a∈N,∀n∈N, ∃l∈N{displaystyle forall ain N,forall nin N, exists lin N} 使得 [(a>1∧n>6∧4∤n)→(l|φ(an−1)∧l≥2n)]{displaystyle [(a>1land n>6land 4nmid n)rightarrow (l|varphi (a^{n}-1)land lgeq 2n)]}
   


4. ∑d∣nμ2(d)φ(d)=nφ(n){displaystyle sum _{dmid n}{frac {mu ^{2}(d)}{varphi (d)}}={frac {n}{varphi (n)}}}


5. ∑1≤k≤n(k,n)=1k=12nφ(n) for n>1{displaystyle sum _{1leq kleq n atop (k,n)=1}!!k={frac {1}{2}}nvarphi (n){text{ for }}n>1}


6. ∑k=1nφ(k)=12(1+∑k=1nμ(k)⌊nk⌋2){displaystyle sum _{k=1}^{n}varphi (k)={frac {1}{2}}left(1+sum _{k=1}^{n}mu (k)leftlfloor {frac {n}{k}}rightrfloor ^{2}right)}


7. ∑k=1nφ(k)k=∑k=1nμ(k)k⌊nk⌋{displaystyle sum _{k=1}^{n}{frac {varphi (k)}{k}}=sum _{k=1}^{n}{frac {mu (k)}{k}}leftlfloor {frac {n}{k}}rightrfloor }


8. ∑k=1nkφ(k)=O(n){displaystyle sum _{k=1}^{n}{frac {k}{varphi (k)}}={mathcal {O}}(n)}


9. ∑k=1n1φ(k)=O(log⁡(n)){displaystyle sum _{k=1}^{n}{frac {1}{varphi (k)}}={mathcal {O}}(log(n))}

与欧拉函数有关的不等式

1. 
   φ(n)>neγlog⁡log⁡n+3log⁡log⁡n{displaystyle varphi (n)>{frac {n}{e^{gamma };log log n+{frac {3}{log log n}}}}}，其中n > 2，γ 为欧拉-马歇罗尼常数。


2. 
   φ(n)≥n2{displaystyle varphi (n)geq {sqrt {frac {n}{2}}}} ，其中n > 0。


3. 对整数n > 6，φ(n)≥n{displaystyle varphi (n)geq {sqrt {n}}}。


4. 当n为质数时，显然有φ(n)=n−1{displaystyle varphi (n)=n-1}。对于合数的n，则有：

φ(n)≤n−n{displaystyle varphi (n)leq n-{sqrt {n}}}

参考来源

• Milton Abramowitz、Irene A. Stegun， Handbook of Mathematical Functions， (1964) Dover Publications , New York. ISBN 0-486-61272-4. 24.3.2节.

• Eric Bach、Jeffrey Shallit， Algorithmic Number Theory, 卷 1, 1996, MIT Press. ISBN 0-262-02405-5, 8.8节，234页.

• Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311.

• 柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001

文獻来源

1. 
   ^ Where does the word “totient” come from?
   


2. 
   ^ Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608
   


3. 
   ^ Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814