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

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

例如，因為1、3、5和7均與8互質。

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

歷史：欧拉函數與費馬小定理
1736年，欧拉證明了费马小定理：
:假若 p 為質數，a 為任意正整數，那麼 a^p - a 可被 p 整除。
然後欧拉予以一般化：
:假若 a 與 n 互質，那麼 a^{\varphi(n)} - 1 可被 n 整除。亦即，a^{\varphi(n)} \equiv 1 \pmod n。
其中 \varphi(n) 即為歐拉總計函數。如果 n 為質數，那麼 \varphi(n) = n - 1，因此，有高斯的版本：
:假若 p 為質數，a 與 p 互質（a 不是 p 的倍數），那麼 a^{p-1} \equiv 1 \pmod p。

欧拉函數的值
以下為n 為1至100時，對應\varphi(n) 的值
:

若n有標準分解p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}（其中各p_i為互異的質因子，各k_i \ge 1為質因子的次數），則歐拉函數在該處的值為
:\varphi(n) = p_1^{k_1-1} p_2^{k_2 - 1} \cdots p_r^{k_r - 1} (p_1 - 1) (p_2 - 1) \cdots (p_r - 1),

亦可等價地寫成
:\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right).
此結果可由\varphi在質數冪處的取值，以及其積性得到。

質數冪處取值
最簡單的情況有\varphi(1) =1 （小于等于1的正整数中唯一和1互質的數就是1本身）。

一般地，若n是質數p的k次冪，則\varphi(n)=\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1}，因為除了p的倍數外，其他數都跟n互質。

積性
歐拉函數是積性函數，即是说若m,n互質，則\varphi(mn)=\varphi(m)\varphi(n)。使用中國剩餘定理有較簡略的證明：設A, B, C是跟m, n, mn互質的數的集，據中國剩餘定理，A \times B和C可建立雙射（一一對應）關係，因此兩者元素個數相等。

較詳細的證明如下：

設N，且N=k_1m+p=k_2n+q。若N與mn互質，則N與m、n均互質。又因為(k_1m+p,m)=(p,m),(k_2n+q,n)=(q,n)，若p,q分別與m,n互質，則N一定和mn互質。反之亦然，即若N與mn互質，則亦有p,q分別與m,n互質。

由中國剩餘定理，方程組
:\left\{ \begin{matrix} N \equiv p \pmod {m} \\ N \equiv q \pmod {n} \\ \end{matrix} \right.

的通解可以寫成N=kmn+pt_1n+qt_2m \ (k \in \mathbb Z), 其中t_1, t_2為固定的整數，故二元組(p,q)（要滿足0 ）與小於mn且與mn互質的正整數N一一對應。

由\varphi的定義（和乘法原理），前一種數對(p,q)的個數為\varphi(m)\varphi(n)。而後一種數N的個數為\varphi(mn)。

所以，\varphi(mn)=\varphi(m)\varphi(n).

公式的證明
結合以上兩小節的結果可得：若n有質因數分解式n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}，則

-{zh-hant:
\quad\begin{align}\varphi(n) &= \varphi\left(\prod_{i=1}^r p_i^{k_i}\right) \\
&= \prod_{i=1}^r \varphi\left(p_i^{k_i}\right) &\text{（積性）}\\
&= \prod_{i=1}^r p_i^{k_i-1}(p_i-1) &\text{（質數冪處取值）} \\
&= n\prod_{i = 1}^r \left(1-\frac{1}{p_i}\right).\end{align};
zh-hans:
\quad\begin{align}\varphi(n) &= \varphi\left(\prod_{i=1}^r p_i^{k_i}\right) \\
&= \prod_{i=1}^r \varphi\left(p_i^{k_i}\right) &\text{（积性）}\\
&= \prod_{i=1}^r p_i^{k_i-1}(p_i-1) &\text{（质数幂处取值）} \\
&= n\prod_{i = 1}^r \left(1-\frac{1}{p_i}\right).\end{align};
}-

例子
計算72 = 2^3 \times 3^2的歐拉函數值：
:\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24.

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

其中的d为n的正约数。

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

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

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

對任何兩個互質的正整數a, m（即 gcd(a,m) = 1），m\ge2，有
:a^{\varphi(m)} \equiv 1 \pmod m
即欧拉定理。

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

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

歐拉商數
歐拉商數（totient number）指的是歐拉函數的值，也就是說，若是一個歐拉商數，那至少存在一個，使得。而歐拉商數的「重複度」（valency或multiplicity），指的是這等式的解數。相對地，一個非歐拉商數指的是不是歐拉商數的自然數。顯然所有大於1的奇數都是非歐拉商數，此外也存有無限多的偶數是非歐拉商數，且所有的正整數都有一個倍數是非歐拉商數。

不大於的歐拉商數個數可由以下公式給出：
:\frac{x}{\log x}e^{ \big(C+o(1)\big)(\log\log\log x)^2 }

其中。

考慮重複度，那麼不大於的歐拉商數個數可由以下公式給出：

:\Big\vert\{ n : \varphi(n) \le x \}\Big\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x)

其中對任意正數而言，誤差項至多與成比例。

目前已知對於任意的而言，有無限多個，其重複度超過。

Ford定理
證明說對於任意整數而言，總存在一個歐拉商數，其重複度為，也就是說總有數字使得這等式有剛好個解。這結果由瓦茨瓦夫·謝爾賓斯基所猜測，且是的一個結果。

完全歐拉商數
完全歐拉商數（perfect totient number）是一個等同於其歐拉函數迭代總和的整數，也就是說，如果將歐拉函數套用在一個正整數n之後，並將歐拉函數套用在如此所得的結果上，如此下去，直到最後得到1為止，並將這一系列的數給加總起來。若這總和為n，那麼n就是一個完全歐拉商數。

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

由\varphi(n)生成的狄利克雷级数是：

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

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

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

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

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

其对于满足 |q|\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}

后者等价于：

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

欧拉函数的走势
随着n变大，估计\varphi(n) 的值是一件很难的事。当n为质数时，\varphi(n)=n-1，但有时\varphi(n)又与n差得很远。

在n足够大时，有估计：
:对每个 ε > 0，都有n > N(ε)使得 \,n^{1-\varepsilon}

如果考虑比值：

:\,\varphi(n)/n,

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

\varphi就平均值的意义上来说是与n很相近的，因为：
:\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/\pi^2 。一个相关的结果是比值\varphi(n)/n的平均值：

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

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

\;\varphi\left(n^m\right) = n^{m-1}\varphi(n)

\forall a \in N , \forall n \in N , \ \exists l \in N 使得 [(a >1 \land n > 1)\rightarrow (l|\varphi(a^n-1) \land l \geq n) ]

\forall a \in N , \forall n \in N , \ \exists l \in N 使得 [(a >1 \land n > 6 \land 4 \nmid n )\rightarrow (l|\varphi(a^n-1) \land l \geq 2n) ]

\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}

\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1

\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)

\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor

\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)

\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))

与欧拉函数有关的不等式
#
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
，其中n > 2，γ 为欧拉-马歇罗尼常数。
#
\varphi(n) \ge \sqrt{\frac {n} {2} }
，其中n > 0。

对整数n > 6，

\varphi(n) \ge \sqrt{n}
。

当n为质数时，显然有\varphi(n) = n-1。对于合数的n，则有：

:
\varphi(n) \le n-\sqrt{n}

未解決問題
萊默的歐拉函數問題
若是質數，則有。1932年，德里克·亨利·萊默問說是否有合成數使得整除。目前未知是否有這樣的數存在。

1933年萊默證明說若有這樣的n，那麼n必然是奇數、必然是無平方因子數，且必然有至少七個不同的質因數（\omega(n)\ge7）。1980年，Cohen和Hagis證明了說，若這樣的n存在，則n > 10^{20}且n有至少14個不同的質因數（\omega(n)\ge14）；此外，Hagis證明了說若這樣的n存在且可被3除盡，那麼n > 10^{1937042}且n有至少298848個不同的質因數（\omega(n)\ge298848）。

卡邁克爾猜想的歐拉函數猜想
此猜想認為說不存在正整數，使得對於所有其他的而言，在的狀況下必有。可見上述Ford定理一節的說明。

若有一個如此的反例存在，就必有無限多的反例存在，而最小的可能反例，在十進位下，其位數超過一百億。

程式代码
C++
template
inline T phi(T n) {
T ans = n;
for (T i = 2; i i 1) ans = ans / n (n - 1);
return ans;
}

参考来源

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

文獻来源
參考資料

欧拉函数