此條目頁的主題是小於等於
n 的正整數中與
n 互質 的數的數目。關於形式為
ϕ
(
q
)
=
∏
k
=
1
∞
(
1
−
q
k
)
{\displaystyle \phi (q)=\prod _{k=1}^{\infty }(1-q^{k})}
的函數，請見「
歐拉函數 (複變函數) 」。
在數論 中，對正整數 n ，歐拉函數
φ
(
n
)
{\displaystyle \varphi (n)}
n 的正整數中與n 互質 的數的數目。此函數 以其首名研究者歐拉 命名，它又稱為φ函數 （由高斯 所命名）或是歐拉總計函數 [ 1] 西爾維斯特 所命名）。
當n 為1至1000的整數時
φ
(
n
)
{\displaystyle \varphi (n)}
例如
φ
(
8
)
=
4
{\displaystyle \varphi \left(8\right)=4}
互質 。
歐拉函數實際上是模n 的同餘類 所構成的乘法群 （即環
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
單位元 組成的乘法群）的階 。這個性質與拉格朗日定理 一起構成了歐拉定理 的證明。
最簡單的情況有
φ
(
1
)
=
1
{\displaystyle \varphi (1)=1}
一般地，若n 是質數 p 的k 次冪 ，則
φ
(
n
)
=
φ
(
p
k
)
=
p
k
−
p
k
−
1
=
(
p
−
1
)
p
k
−
1
{\displaystyle \varphi (n)=\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}
p 的倍數 外，其他數都跟n 互質。
歐拉函數是積性函數 ，即是說若m ,n 互質，則
φ
(
m
n
)
=
φ
(
m
)
φ
(
n
)
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}
中國剩餘定理 有較簡略的證明：設A , B , C 是跟m , n , mn 互質的數的集，據中國剩餘定理 ，
A
×
B
{\displaystyle A\times B}
C
{\displaystyle C}
雙射 （一一對應）關係，因此兩者元素個數相等。
較詳細的證明如下：
設
N
<
m
n
{\displaystyle N<mn}
N
=
k
1
m
+
p
=
k
2
n
+
q
{\displaystyle N=k_{1}m+p=k_{2}n+q}
N
{\displaystyle N}
m
n
{\displaystyle mn}
N
{\displaystyle N}
m
{\displaystyle m}
n
{\displaystyle n}
(
k
1
m
+
p
,
m
)
=
(
p
,
m
)
,
(
k
2
n
+
q
,
n
)
=
(
q
,
n
)
{\displaystyle (k_{1}m+p,m)=(p,m),(k_{2}n+q,n)=(q,n)}
p
,
q
{\displaystyle p,q}
m
,
n
{\displaystyle m,n}
N
{\displaystyle N}
m
n
{\displaystyle mn}
N
{\displaystyle N}
m
n
{\displaystyle mn}
p
,
q
{\displaystyle p,q}
m
,
n
{\displaystyle m,n}
由中國剩餘定理 ，方程組
{
N
≡
p
(
mod
m
)
N
≡
q
(
mod
n
)
{\displaystyle \left\{{\begin{matrix}N\equiv p{\pmod {m}}\\N\equiv q{\pmod {n}}\\\end{matrix}}\right.}
的通解可以寫成
N
=
k
m
n
+
p
t
1
n
+
q
t
2
m
(
k
∈
Z
)
,
{\displaystyle N=kmn+pt_{1}n+qt_{2}m\ (k\in \mathbb {Z} ),}
t
1
,
t
2
{\displaystyle t_{1},t_{2}}
(
p
,
q
)
{\displaystyle (p,q)}
0
<
p
≤
m
,
0
<
q
≤
n
,
(
p
,
m
)
=
1
,
(
q
,
n
)
=
1
{\displaystyle 0<p\leq m,\ 0<q\leq n,\ (p,m)=1,\ (q,n)=1}
m
n
{\displaystyle mn}
m
n
{\displaystyle mn}
N
{\displaystyle N}
由
φ
{\displaystyle \varphi }
乘法原理 ），前一種數對
(
p
,
q
)
{\displaystyle (p,q)}
φ
(
m
)
φ
(
n
)
{\displaystyle \varphi (m)\varphi (n)}
N
{\displaystyle N}
φ
(
m
n
)
{\displaystyle \varphi (mn)}
所以，
φ
(
m
n
)
=
φ
(
m
)
φ
(
n
)
.
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}
結合以上兩小節的結果可得：若
n
{\displaystyle n}
質因數分解式
n
=
p
1
k
1
p
2
k
2
⋯
p
r
k
r
{\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}
φ
(
n
)
=
φ
(
∏
i
=
1
r
p
i
k
i
)
=
∏
i
=
1
r
φ
(
p
i
k
i
)
（ 積 性 ）
=
∏
i
=
1
r
p
i
k
i
−
1
(
p
i
−
1
)
（ 質 數 冪 處 取 值 ）
=
n
∏
i
=
1
r
(
1
−
1
p
i
)
.
{\displaystyle \quad {\begin{aligned}\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{aligned}}}
計算
72
=
2
3
×
3
2
{\displaystyle 72=2^{3}\times 3^{2}}
φ
(
72
)
=
φ
(
2
3
×
3
2
)
=
2
3
−
1
(
2
−
1
)
×
3
2
−
1
(
3
−
1
)
=
2
2
×
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 1\times 3\times 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 _{d\mid n}\varphi (d)=n}
其中的d 為n 的正約數。
運用默比烏斯反轉公式 來「翻轉」這個和，就可以得到另一個關於
φ
(
n
)
{\displaystyle \varphi (n)}
φ
(
n
)
=
∑
d
∣
n
d
⋅
μ
(
n
/
d
)
{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)}
其中 μ 是所謂的默比烏斯函數 ，定義在正整數 上。
對任何兩個互質 的正整數a , m （即 gcd(a ,m ) = 1），
m
≥
2
{\displaystyle m\geq 2}
a
φ
(
m
)
≡
1
(
mod
m
)
{\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}
即歐拉定理 。
這個定理可以由群論中的拉格朗日定理 得出，因為任意與m 互質的a 都屬於環
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
Z
/
n
Z
×
{\displaystyle \mathbb {Z} /n\mathbb {Z} ^{\times }}
當m 是質數 p 時，此式則為：
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
即費馬小定理 。
歐拉商數 （totient number）指的是歐拉函數的值，也就是說，若m n φ (n ) = m m [ 4] 非歐拉商數 [ 5] [ 6]
不大於x
x
log
x
e
(
C
+
o
(
1
)
)
(
log
log
log
x
)
2
{\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}
其中C = 0.8178146...[ 7]
考慮重複度，那麼不大於x
|
{
n
:
φ
(
n
)
≤
x
}
|
=
ζ
(
2
)
ζ
(
3
)
ζ
(
6
)
⋅
x
+
R
(
x
)
{\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}
其中對任意正數k R x / (log x )k [ 8]
目前已知對於任意的δ < 0.55655m m δ [ 9] [ 10]
Ford (1999) harvtxt模板錯誤: 無指向目標: CITEREFFord1999 (幫助 ) 證明說對於任意整數k ≥ 2m k φ (n ) = m k 瓦茨瓦夫·謝爾賓斯基 所猜測，[ 11] Schinzel猜想H [ 7] [ 7] [ 10]
然而，沒有任何數字m k = 1卡邁克爾猜想的歐拉函數猜想 m k = 1[ 12]
主條目：完全歐拉商數
完全歐拉商數（perfect totient number）是一個等同於其歐拉函數迭代總和的整數，也就是說，如果將歐拉函數套用在一個正整數
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
φ
(
n
m
)
=
n
m
−
1
φ
(
n
)
{\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}
∀
a
∈
N
,
∀
n
∈
N
,
∃
l
∈
N
{\displaystyle \forall a\in N,\forall n\in N,\ \exists l\in N}
[
(
a
>
1
∧
n
>
1
)
→
(
l
|
φ
(
a
n
−
1
)
∧
l
≥
n
)
]
{\displaystyle [(a>1\land n>1)\rightarrow (l|\varphi (a^{n}-1)\land l\geq n)]}
∀
a
∈
N
,
∀
n
∈
N
,
∃
l
∈
N
{\displaystyle \forall a\in N,\forall n\in N,\ \exists l\in N}
[
(
a
>
1
∧
n
>
6
∧
4
∤
n
)
→
(
l
|
φ
(
a
n
−
1
)
∧
l
≥
2
n
)
]
{\displaystyle [(a>1\land n>6\land 4\nmid n)\rightarrow (l|\varphi (a^{n}-1)\land l\geq 2n)]}
∑
d
∣
n
μ
2
(
d
)
φ
(
d
)
=
n
φ
(
n
)
{\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}
∑
1
≤
k
≤
n
(
k
,
n
)
=
1
k
=
1
2
n
φ
(
n
)
for
n
>
1
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}n>1}
∑
k
=
1
n
φ
(
k
)
=
1
2
(
1
+
∑
k
=
1
n
μ
(
k
)
⌊
n
k
⌋
2
)
{\displaystyle \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)}
∑
k
=
1
n
φ
(
k
)
k
=
∑
k
=
1
n
μ
(
k
)
k
⌊
n
k
⌋
{\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor }
∑
k
=
1
n
k
φ
(
k
)
=
O
(
n
)
{\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\mathcal {O}}(n)}
∑
k
=
1
n
1
φ
(
k
)
=
O
(
log
(
n
)
)
{\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\mathcal {O}}(\log(n))}
φ
(
n
)
>
n
e
γ
log
log
n
+
3
log
log
n
{\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}}
n > 2，γ 為歐拉-馬歇羅尼常數 。
φ
(
n
)
≥
n
2
{\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}
n > 0。對整數n > 6，
φ
(
n
)
≥
n
{\displaystyle \varphi (n)\geq {\sqrt {n}}}
當n 為質數時，顯然有
φ
(
n
)
=
n
−
1
{\displaystyle \varphi (n)=n-1}
合數 的n ，則有：
φ
(
n
)
≤
n
−
n
{\displaystyle \varphi (n)\leq n-{\sqrt {n}}}
主條目：卡邁克爾猜想的歐拉函數猜想
此猜想認為說不存在正整數n m m ≠ n φ (m ) ≠ φ (n )Ford定理 一節的說明。
若有一個如此的反例存在，就必有無限多的反例存在，而最小的可能反例，在十進位下，其位數超過一百億。[ 4]
黎曼猜想 成立，當且僅當以下不等式對所有的n ≥ p 120569 #p 120569 #120569 質數的乘積 ：
n
φ
(
n
)
<
e
γ
log
log
n
+
e
γ
(
4
+
γ
−
log
4
π
)
log
n
{\displaystyle {\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}}
此處的γ 歐拉常數 。[ 17]
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 ;
}
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頁. 柯召，孫琦：數論講義（上冊），第二版，高等教育出版社，2001
Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608
Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814
Sándor & Crstici (2004) p.230
Sándor & Crstici (2004) p.229
Sándor & Crstici (2004) p.228
Cohen, Graeme L.; Hagis, Peter Jr. On the number of prime factors of n φ (n )n − 128 : 177–185. ISSN 0028-9825 Zbl 0436.10002 Broughan, Kevin. Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents First. Cambridge University Press. 2017. ISBN 978-1-107-19704-6 Corollary 5.35 
![{\displaystyle [(a>1\land n>1)\rightarrow (l|\varphi (a^{n}-1)\land l\geq n)]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/580703fbafb9bc0f881425b2a65ce95e2c98eeb7)
![{\displaystyle [(a>1\land n>6\land 4\nmid n)\rightarrow (l|\varphi (a^{n}-1)\land l\geq 2n)]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/d7f52bf7a4c789d0247a5b71dd96b059946233fa)
