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

{{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>{{Cite web |url=http://english.stackexchange.com/questions/23694/where-does-the-word-totient-come-from |title=Where does the word “totient” come from? |accessdate=2014-10-16 |archive-date=2014-10-12 |archive-url=https://web.archive.org/web/20141012052153/http://english.stackexchange.com/questions/23694/where-does-the-word-totient-come-from |dead-url=no }}</ref>（totient function，由[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]所命名）。

例如{{計算結果|eulerphi(8)}}，因為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>n</math> 為<math>1</math>至<math>100</math>時，對應<math>\varphi(n)</math> 的值
:{| class="wikitable" style="text-align: right"
|+{{math|''φ''(''n'')}} for {{math|1 ≤ ''n'' ≤ 100}}
! +
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|- 
! 0 
| 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 
|-
! 10
| 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 
|- 
! 20
| 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 
|-
! 30
| 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 
|-
! 40
| 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20
|-
! 50
| 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 
|-
! 60
| 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 
|-
! 70
| 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32
|-
! 80
| 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24
|-
! 90
| 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40 
|}

若<math>n</math>有[[算術基本定理|標準分解]]<math>p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}</math>（其中各<math>p_i</math>為互異的質因子，各<math>k_i \ge 1</math>為質因子的次數），則歐拉函數在該處的值為
:<math>\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),</math>

亦可等價地寫成
:<math>\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).</math>
此結果可由<math>\varphi</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>N<mn</math>，且<math>N=k_1m+p=k_2n+q</math>。若<math>N</math>與<math>mn</math>互質，則<math>N</math>與<math>m</math>、<math>n</math>均互質。又因為<math>(k_1m+p,m)=(p,m),(k_2n+q,n)=(q,n)</math>，若<math>p,q</math>分別與<math>m,n</math>互質，則<math>N</math>一定和<math>mn</math>互質。反之亦然，即若<math>N</math>與<math>mn</math>互質，則亦有<math>p,q</math>分別與<math>m,n</math>互質。

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

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

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

所以，<math>\varphi(mn)=\varphi(m)\varphi(n).</math>

===公式的證明===
結合以上兩小節的結果可得：若<math>n</math>有[[算術基本定理|質因數分解式]]<math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}</math>，則

-{zh-hant:
<math>\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}</math>;
zh-hans:
<math>\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}</math>;
}-

===例子===
計算<math>72 = 2^3 \times 3^2</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>
即[[費馬小定理]]。

==歐拉商數==
'''歐拉商數'''（totient number）指的是歐拉函數的值，也就是說，若{{mvar|m}}是一個歐拉商數，那至少存在一個{{mvar|n}}，使得{{math|''φ''(''n'') {{=}} ''m''}}。而歐拉商數{{mvar|m}}的「重複度」（valency或multiplicity），指的是這等式的解數。<ref name=Guy144>Guy (2004) p.144</ref>相對地，一個'''[[非歐拉商數]]'''指的是不是歐拉商數的自然數。顯然所有大於1的奇數都是非歐拉商數，此外也存有無限多的偶數是非歐拉商數，<ref name=SC230>Sándor & Crstici (2004) p.230</ref>且所有的正整數都有一個倍數是非歐拉商數。<ref name=Zha1993>{{cite journal | zbl=0772.11001 | last=Zhang | first=Mingzhi | title=On nontotients | journal=[[Journal of Number Theory]] | volume=43 | number=2 | pages=168–172 | year=1993 | issn=0022-314X | doi=10.1006/jnth.1993.1014| doi-access=free }}</ref>

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

其中{{math|''C'' {{=}} 0.8178146...}}。<ref name=Ford1998>{{cite journal | zbl=0914.11053 | last=Ford | first=Kevin | title=The distribution of totients | journal=Ramanujan J. | series=Developments in Mathematics | volume=2 | number=1–2 | pages=67–151 | year=1998 | issn=1382-4090 | doi=10.1007/978-1-4757-4507-8_8| arxiv=1104.3264 | isbn=978-1-4419-5058-1 }}</ref>

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

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

其中對任意正數{{mvar|k}}而言，誤差項{{mvar|R}}至多與{{math|{{sfrac|''x''|(log ''x'')<sup>''k''</sup>}}}}成比例。<ref name=SMC22>Sándor et al (2006) p.22</ref>

目前已知對於任意的{{math|''δ'' < 0.55655}}而言，有無限多個{{mvar|m}}，其重複度超過{{math|''m''<sup>''δ''</sup>}}。<ref name=SMC21>Sándor et al (2006) p.21</ref><ref name=Guy145>Guy (2004) p.145</ref>

===Ford定理===
{{harvtxt|Ford|1999}}證明說對於任意整數{{math|''k'' ≥ 2}}而言，總存在一個歐拉商數{{mvar|m}}，其重複度為{{mvar|k}}，也就是說總有數字使得這等式{{math|''φ''(''n'') {{=}} ''m''}}有剛好{{mvar|k}}個解。這結果由[[瓦茨瓦夫·謝爾賓斯基]]所猜測，<ref name=SC229>Sándor & Crstici (2004) p.229</ref>且是{{link-en|Schinzel猜想H|Schinzel's hypothesis H}}的一個結果。<ref name=Ford1998/>事實上，對於任何出現的重複度而言，該重複度會出現無限多次。<ref name=Ford1998/><ref name=Guy145/>

然而，沒有任何數字{{mvar|m}}的重複度為{{math|''k'' {{=}} 1}}。{{link-en|卡邁克爾猜想的歐拉函數猜想|Carmichael's totient function conjecture}}講的是沒有{{mvar|m}}的重複度為{{math|''k'' {{=}} 1}}。<ref name=SC228>Sándor & Crstici (2004) p.228</ref>

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

== 未解決問題 ==
=== 萊默的歐拉函數問題 ===
{{main article|萊默的歐拉函數問題}}

若{{mvar|p}}是質數，則有{{math|''φ''(''p'') {{=}} ''p'' − 1}}。1932年，[[德里克·亨利·萊默]]問說是否有合成數{{mvar|n}}使得{{math|''φ''(''n'') }}整除{{math|''n'' − 1}}。目前未知是否有這樣的數存在。<ref>Ribenboim, pp. 36–37.</ref>

1933年萊默證明說若有這樣的<math>n</math>，那麼<math>n</math>必然是奇數、必然是[[無平方因子數]]，且必然有至少七個不同的質因數（<math>\omega(n)\ge7</math>）。1980年，Cohen和Hagis證明了說，若這樣的<math>n</math>存在，則<math>n > 10^{20}</math>且<math>n</math>有至少14個不同的質因數（<math>\omega(n)\ge14</math>）；<ref>{{cite journal | zbl=0436.10002 | last1=Cohen | first1=Graeme L. | last2=Hagis | first2=Peter Jr. | title=On the number of prime factors of {{mvar|n}} if {{math|''φ''(''n'')}} divides {{math|''n'' − 1}} | journal=Nieuw Arch. Wiskd. |series=III Series | volume=28 | pages=177–185 | year=1980 | issn=0028-9825 }}</ref>此外，Hagis證明了說若這樣的<math>n</math>存在且可被3除盡，那麼<math>n > 10^{1937042}</math>且<math>n</math>有至少298848個不同的質因數（<math>\omega(n)\ge298848</math>）。<ref>{{cite journal | zbl=0668.10006 | last=Hagis | first=Peter Jr. | title=On the equation {{math|''M''·φ(''n'') {{=}} ''n'' − 1}} | journal=Nieuw Arch. Wiskd. |series=IV Series | volume=6 | number=3 | pages=255–261 | year=1988 | issn=0028-9825 }}</ref><ref name=Guy142>Guy (2004) p.142</ref>

===卡邁克爾猜想的歐拉函數猜想===
{{main article|卡邁克爾猜想的歐拉函數猜想}}

此猜想認為說不存在正整數{{mvar|n}}，使得對於所有其他的{{mvar|m}}而言，在{{math|''m'' ≠ ''n''}}的狀況下必有{{math|''φ''(''m'') ≠ ''φ''(''n'')}}。可見上述[[#Ford定理|Ford定理]]一節的說明。

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

===黎曼猜想===
[[黎曼猜想]]成立，當且僅當以下不等式對所有的{{math|''n'' ≥ ''p''<sub>120569</sub>#}}成立。此處的{{math|''p''<sub>120569</sub>#}}是最初的{{math|120569}}個[[質數階乘|質數的乘積]]：
:<math>\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}</math>
此處的{{mvar|γ}}是[[歐拉常數]]。<ref>{{Cite book |last1=Broughan |first1=Kevin |title=Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents |publisher=Cambridge University Press |year=2017 |edition=First |isbn=978-1-107-19704-6}} Corollary 5.35</ref>

==程式代码==

===C++===
<syntaxhighlight lang="c++" line="1">
template <typename T>
inline T phi(T n) {
    T ans = n;
    for (T i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
</syntaxhighlight>

== 参考来源 ==
* 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.] {{Wayback|url=http://www.math.uiuc.edu/~ford/wwwpapers/sierp.pdf |date=20080905113032 }}

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

== 參考資料 ==
{{reflist}}

[[Category:同余]]
[[Category:积性函数]]
[[Category:包含证明的条目]]
[[Category:代数]]
[[Category:数论]]
[[Category:莱昂哈德·欧拉]]