此條目頁的主題是小於等於
n 的正整數中與
n 互質 的數的數目。關於形式為
ϕ
(
q
)
=
∏
k
=
1
∞
(
1
−
q
k
)
{\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 \left(8\right)=4}
,因為1、3、5和7均與8互質 。
歐拉函數實際上是模n 的同餘類 所構成的乘法群 (即環
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
的所有單位元 組成的乘法群)的階 。這個性質與拉格朗日定理 一起構成了歐拉定理 的證明。
歷史:歐拉函數與費馬小定理
1736年,歐拉證明了費馬小定理 [ 2] :
假若
p
{\displaystyle p}
為質數,
a
{\displaystyle a}
為任意正整數,那麼
a
p
−
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
(
mod
n
)
{\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}
的倍數),那麼
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
。
歐拉函數的值
以下為
n
{\displaystyle n}
為
1
{\displaystyle 1}
至
100
{\displaystyle 100}
時,對應
φ
(
n
)
{\displaystyle \varphi (n)}
的值
φ (n ) for 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
若
n
{\displaystyle n}
有標準分解
p
1
k
1
p
2
k
2
⋯
p
r
k
r
{\displaystyle p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}
(其中各
p
i
{\displaystyle p_{i}}
為互異的質因子,各
k
i
≥
1
{\displaystyle k_{i}\geq 1}
為質因子的次數),則歐拉函數在該處的值為
φ
(
n
)
=
p
1
k
1
−
1
p
2
k
2
−
1
⋯
p
r
k
r
−
1
(
p
1
−
1
)
(
p
2
−
1
)
⋯
(
p
r
−
1
)
,
{\displaystyle \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),}
亦可等價地寫成
φ
(
n
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
⋯
(
1
−
1
p
r
)
.
{\displaystyle \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).}
此結果可由
φ
{\displaystyle \varphi }
在質數冪處的取值,以及其積性 得到。
質數冪處取值
最簡單的情況有
φ
(
1
)
=
1
{\displaystyle \varphi (1)=1}
(小於等於1的正整數中唯一和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 的「重複度」(valency或multiplicity),指的是這等式的解數。[ 4] 相對地,一個非歐拉商數 指的是不是歐拉商數的自然數。顯然所有大於1的奇數都是非歐拉商數,此外也存有無限多的偶數是非歐拉商數,[ 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.55655 而言,有無限多個m ,其重複度超過m δ 。[ 9] [ 10]
Ford定理
Ford (1999 )證明說對於任意整數k ≥ 2 而言,總存在一個歐拉商數m ,其重複度為k ,也就是說總有數字使得這等式φ (n ) = m 有剛好k 個解。這結果由瓦茨瓦夫·謝爾賓斯基 所猜測,[ 11] 且是Schinzel猜想H 的一個結果。[ 7] 事實上,對於任何出現的重複度而言,該重複度會出現無限多次。[ 7] [ 10]
然而,沒有任何數字m 的重複度為k = 1 。卡邁克爾猜想的歐拉函數猜想 講的是沒有m 的重複度為k = 1 。[ 12]
完全歐拉商數
完全歐拉商數(perfect totient number)是一個等同於其歐拉函數迭代總和的整數,也就是說,如果將歐拉函數套用在一個正整數
n
{\displaystyle n}
之後,並將歐拉函數套用在如此所得的結果上,如此下去,直到最後得到1為止,並將這一系列的數給加總起來。若這總和為
n
{\displaystyle n}
,那麼
n
{\displaystyle n}
就是一個完全歐拉商數。
生成函數
以下兩個由歐拉函數生成的級數都是來自於上節所給出的性質:
∑
d
|
n
φ
(
d
)
=
n
{\displaystyle \sum _{d|n}\varphi (d)=n}
。
由
φ
{\displaystyle \varphi }
(n )生成的狄利克雷級數 是:
∑
n
=
1
∞
φ
(
n
)
n
s
=
ζ
(
s
−
1
)
ζ
(
s
)
.
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}
其中ζ(s )是黎曼ζ函數 。推導過程如下:
ζ
(
s
)
∑
f
=
1
∞
φ
(
f
)
f
s
=
(
∑
g
=
1
∞
1
g
s
)
(
∑
f
=
1
∞
φ
(
f
)
f
s
)
{\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
∞
(
∑
f
g
=
h
1
⋅
φ
(
g
)
)
1
h
s
{\displaystyle .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum _{h=1}^{\infty }\left(\sum _{fg=h}1\cdot \varphi (g)\right){\frac {1}{h^{s}}}}
.
=
∑
h
=
1
∞
(
∑
f
g
=
h
φ
(
g
)
)
1
h
s
=
∑
h
=
1
∞
(
∑
d
|
h
φ
(
d
)
)
1
h
s
{\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
)
)
1
h
s
=
∑
h
=
1
∞
h
h
s
{\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
∞
h
h
s
=
ζ
(
s
−
1
)
{\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}=\zeta (s-1)}
歐拉函數生成的朗貝級數 如下:
∑
n
=
1
∞
φ
(
n
)
q
n
1
−
q
n
=
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
)
q
n
1
−
q
n
=
∑
n
=
1
∞
φ
(
n
)
∑
r
≥
1
q
r
n
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}=\sum _{n=1}^{\infty }\varphi (n)\sum _{r\geq 1}q^{rn}}
後者等價於:
∑
k
≥
1
q
k
∑
n
|
k
φ
(
n
)
=
∑
k
≥
1
k
q
k
=
q
(
1
−
q
)
2
.
{\displaystyle \sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 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 (ε)使得
n
1
−
ε
<
φ
(
n
)
<
n
{\displaystyle \,n^{1-\varepsilon }<\varphi (n)<n}
如果考慮比值:
φ
(
n
)
/
n
,
{\displaystyle \,\varphi (n)/n,}
由以上已經提到的公式,可以得到其值等於類似
1
−
p
−
1
{\displaystyle 1-p^{-1}}
的項的乘積。因此,使比值小的n 將是兩兩不同的質數的乘積。由素數定理 可以知道,常數 ε 可以被替換為:
C
log
log
n
/
log
n
.
{\displaystyle C\,\log \log n/\log n.}
φ
{\displaystyle \varphi }
就平均值的意義上來說是與n 很相近的,因為:
1
n
2
∑
k
=
1
n
φ
(
k
)
=
3
π
2
+
O
(
log
n
n
)
{\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}
的平均值:
1
n
∑
k
=
1
n
φ
(
k
)
k
=
6
π
2
+
O
(
log
n
n
)
.
{\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {6}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right).}
其他與歐拉函數有關的等式
φ
(
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}}}
未解決問題
萊默的歐拉函數問題
若p 是質數,則有φ (p ) = p − 1 。1932年,德里克·亨利·萊默 問說是否有合成數n 使得φ (n ) 整除n − 1 。目前未知是否有這樣的數存在。[ 13]
1933年萊默證明說若有這樣的
n
{\displaystyle n}
,那麼
n
{\displaystyle n}
必然是奇數、必然是無平方因子數 ,且必然有至少七個不同的質因數(
ω
(
n
)
≥
7
{\displaystyle \omega (n)\geq 7}
)。1980年,Cohen和Hagis證明了說,若這樣的
n
{\displaystyle n}
存在,則
n
>
10
20
{\displaystyle n>10^{20}}
且
n
{\displaystyle n}
有至少14個不同的質因數(
ω
(
n
)
≥
14
{\displaystyle \omega (n)\geq 14}
);[ 14] 此外,Hagis證明了說若這樣的
n
{\displaystyle n}
存在且可被3除盡,那麼
n
>
10
1937042
{\displaystyle n>10^{1937042}}
且
n
{\displaystyle n}
有至少298848個不同的質因數(
ω
(
n
)
≥
298848
{\displaystyle \omega (n)\geq 298848}
)。[ 15] [ 16]
卡邁克爾猜想的歐拉函數猜想
此猜想認為說不存在正整數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]
程式代碼
C++
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
文獻來源
參考資料
^ Where does the word “totient” come from? . [2014-10-16 ] . (原始內容存檔 於2014-10-12).
^ Mathematical Thought From Ancient to Modern Times, 第 2 卷,p.608
^ Mathematical Thought From Ancient to Modern Times, 第 3 卷,p.814
^ 4.0 4.1 Guy (2004) p.144
^ Sándor & Crstici (2004) p.230
^ Zhang, Mingzhi. On nontotients. Journal of Number Theory . 1993, 43 (2): 168–172. ISSN 0022-314X . Zbl 0772.11001 . doi:10.1006/jnth.1993.1014 .
^ 7.0 7.1 7.2 Ford, Kevin. The distribution of totients. Ramanujan J. Developments in Mathematics. 1998, 2 (1–2): 67–151. ISBN 978-1-4419-5058-1 . ISSN 1382-4090 . Zbl 0914.11053 . arXiv:1104.3264 . doi:10.1007/978-1-4757-4507-8_8 .
^ Sándor et al (2006) p.22
^ Sándor et al (2006) p.21
^ 10.0 10.1 Guy (2004) p.145
^ Sándor & Crstici (2004) p.229
^ Sándor & Crstici (2004) p.228
^ Ribenboim, pp. 36–37.
^ Cohen, Graeme L.; Hagis, Peter Jr. On the number of prime factors of n if φ (n ) divides n − 1 . Nieuw Arch. Wiskd. III Series. 1980, 28 : 177–185. ISSN 0028-9825 . Zbl 0436.10002 .
^ Hagis, Peter Jr. On the equation M ·φ(n ) = n − 1 . Nieuw Arch. Wiskd. IV Series. 1988, 6 (3): 255–261. ISSN 0028-9825 . Zbl 0668.10006 .
^ Guy (2004) p.142
^ 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