此条目页的主題是小於等於
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 (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]
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