查看“欧拉函数”的源代码

{{Otheruses|subject=小於或等於''n''的正整數中與''n''[[互質]]的數的數目|other=形式為<math>\phi(q)=\prod_{k=1}^\infty (1-q^k)</math>的函數|歐拉函數 (複變函數)}}

[[File:EulerPhi.svg|thumb|400px|right|当''n''为1至1000的整数时<math>\varphi(n)</math>的值]]
在[[數論]]中，對正[[整數]]''n''，'''歐拉函數'''<math>\varphi(n)</math>是小於或等於''n''的正整數中與''n''[[互質]]的數的數目。此[[函數 (數學)|函數]]以其首名研究者[[歐拉]]命名，它又稱為'''φ函數'''（由[[卡爾·弗里德里希·高斯|高斯]]所命名）或是'''歐拉總計函數'''<ref>[http://english.stackexchange.com/questions/23694/where-does-the-word-totient-come-from Where does the word “totient” come from?]</ref>（totient function，由[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]所命名）。

例如<math>\varphi(8)=4</math>，因為1,3,5,7均和8互質。

欧拉函数实际上是模''n''的[[同余|同余类]]所构成的乘法[[群]]（即环<math>\mathbb{Z}/n\mathbb{Z}</math>的所有[[单位元]]组成的乘法群）的[[阶 (群论)|阶]]。这个性质与[[拉格朗日定理 (群论)|拉格朗日定理]]一起構成了[[欧拉定理 (数论)|欧拉定理]]的證明。

== 歷史：欧拉函數與費馬小定理 ==
1736年，欧拉證明了[[费马小定理]]<ref>Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608</ref>：
:假若 <math>p</math> 為質數，<math>a</math> 為任意正整數，那麼 <math>a^p - a</math> 可被 <math>p</math> 整除。
然後欧拉予以一般化：
:假若 <math>a</math> 與 <math>n</math> 互質，那麼 <math>a^{\varphi(n)} - 1</math> 可被 <math>n</math> 整除。亦即，<math>a^{\varphi(n)} \equiv 1 \pmod n</math>。
其中 <math>\varphi(n)</math> 即為歐拉總計函數。如果 <math>n</math> 為質數，那麼 <math>\varphi(n) = n - 1</math>，因此，有高斯的版本<ref>Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814</ref>：
:假若 <math>p</math> 為質數，<math>a</math> 與 <math>p</math> 互質（<math>a</math> 不是 <math>p</math> 的倍數），那麼 <math>a^{p-1} \equiv 1 \pmod p</math>。

== 欧拉函數的值 ==
<math>\varphi(1)=1</math>（小于等于1的正整数中唯一和1互質的數就是1本身）。

若''n''是[[質數]]''p''的''k''次[[冪]]，<math>\varphi(n)=\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1}</math>，因為除了''p''的[[倍數]]外，其他數都跟''n''互質。

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

: 若<math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}</math>

: 則<math>\varphi(n) = \prod_{i=1}^r p_i^{k_i-1}(p_i-1) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>。

其中<math>\alpha_p</math>是使得<math>p^{\alpha}</math>整除<math>n</math>的最大整数<math>\alpha</math>（这里<math>\alpha_{p_i} = k_i</math>）。

例如<math>\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24</math>

== 性质 ==
''n''的欧拉函数<math>\varphi(n)</math> 也是[[循环群]] ''C''<sub>''n''</sub> 的[[生成元]]的个数（也是''n''阶[[分圆多项式]]的次数）。''C''<sub>''n''</sub> 中每个元素都能生成 ''C''<sub>''n''</sub> 的一个[[子群]]，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， ''C''<sub>''n''</sub> 的所有子群都具有 ''C''<sub>''d''</sub> 的形式，其中''d''[[整除]]''n''（记作''d''&nbsp;|&nbsp;''n''）。因此只要考察''n''的所有[[因数]]''d''，将 ''C''<sub>''d''</sub> 的生成元个数相加，就将得到 ''C''<sub>''n''</sub> 的元素总个数：''n''。也就是说：
:<math>\sum_{d\mid n}\varphi(d)=n</math>

其中的''d''为''n''的正约数。

运用[[默比乌斯反转公式]]来“翻转”这个和，就可以得到另一个关于<math>\varphi(n)</math>的公式：

:<math>\varphi(n)=\sum_{d\mid n} d \cdot \mu(n/d) </math>

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

對任何兩個[[互質]]的正整數''a'', ''m''（即 gcd(''a'',''m'') = 1），<math>m\ge2</math>，有
:<math>a^{\varphi(m)} \equiv 1 \pmod m</math>
即[[欧拉定理 (数论)|欧拉定理]]。

这个定理可以由群论中的[[拉格朗日定理 (群论)|拉格朗日定理]]得出，因为任意与''m''互质的''a''都属于环 <math>\mathbb{Z}/n\mathbb{Z}</math> 的单位元组成的乘法群<math>\mathbb{Z}/n\mathbb{Z}^{\times}</math>

當''m''是[[質數]]''p''時，此式則為：
:<math>a^{p-1} \equiv 1 \pmod p</math>
即[[費馬小定理]]。

== 生成函数 ==

以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：<math>\sum_{d|n} \varphi(d) = n</math>。

由<math>\varphi</math>(''n'')生成的[[狄利克雷级数]]是：

:<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math>

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

:<math>\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)</math>
:<math>.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{h=1}^\infty \left(\sum_{fg=h} 1 \cdot \varphi(g)\right) \frac{1}{h^s}</math>
:<math>.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \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}</math>
:使用开始时的等式，就得到：<math>\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \frac{h}{h^s}</math>
:于是<math>\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1)</math>

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

:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math> 

其对于满足 |''q''|<1 的''q''[[无穷级数|收敛]]。

推导如下：

:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}</math>

后者等价于：

:<math>
\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) =
\sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.</math>

== 欧拉函数的走势 ==
随着''n''变大，估计<math>\varphi(n)</math> 的值是一件很难的事。当''n''为质数时，<math>\varphi(n)=n-1</math>，但有时<math>\varphi(n)</math>又与''n''差得很远。
 
在''n''足够大时，有估计：
:对每个 ε > 0，都有''n'' > ''N''(ε)使得 <math>\,n^{1-\varepsilon}<\varphi(n)<n</math>

如果考虑比值：

:<math>\,\varphi(n)/n,</math>

由以上已经提到的公式，可以得到其值等于类似<math>1-p^{-1}</math>的项的乘积。因此，使比值小的''n''将是两两不同的质数的乘积。由[[素数定理]]可以知道，常数 ε 可以被替换为：
:<math>C\,\log \log n/ \log n.</math>

<math>\varphi</math>就平均值的意义上来说是与''n''很相近的，因为：
:<math>\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)</math>

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

:<math>\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} = 
\frac{6}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right).</math>

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

# <math>\;\varphi\left(n^m\right) = n^{m-1}\varphi(n) </math>
# <math>  \forall a \in N , \forall n \in N , \ \exists l \in N </math> 使得 <math>[(a >1 \land n > 1)\rightarrow (l|\varphi(a^n-1) \land l \geq n) ]</math>
# <math>    \forall a \in N , \forall n \in N , \ \exists l \in N </math> 使得 <math>[(a >1 \land n > 6 \land 4 \nmid n )\rightarrow (l|\varphi(a^n-1) \land l \geq 2n) ]</math>
# <math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math>
# <math>\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1</math>
# <math>\sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)</math>
# <math>\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor</math>
# <math>\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)</math>
# <math>\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))</math>

== 与欧拉函数有关的不等式 ==
# <math>
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
</math>，其中''n'' > 2，γ 为[[欧拉-马歇罗尼常数]]。
# <math>
\varphi(n) \ge \sqrt{\frac {n} {2} }
</math> ，其中''n'' > 0。
# 对整数n > 6，<math>
\varphi(n) \ge \sqrt{n}
</math>。
# 当''n''为质数时，显然有<math>\varphi(n) = n-1</math>。对于[[合数]]的''n''，则有：
:<math>
\varphi(n) \le n-\sqrt{n}
</math>

== 参考来源 ==
* 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页.

* [http://www.math.uiuc.edu/~ford/wwwpapers/sierp.pdf Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311.]

* 柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001
== 文獻来源 ==

[[Category:积性函数]]
[[Category:同余]]