欧拉函数

1736年，欧拉證明了费马小定理[2]：

假若 ${\displaystyle p}$ 為質數，${\displaystyle a}$ 為任意正整數，那麼 ${\displaystyle a^{p}-a}$ 可被 ${\displaystyle p}$ 整除。

然後欧拉予以一般化：

假若 ${\displaystyle a}$ 與 ${\displaystyle n}$ 互質，那麼 ${\displaystyle a^{\varphi (n)}-1}$ 可被 ${\displaystyle n}$ 整除。亦即，${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$。

其中 ${\displaystyle \varphi (n)}$ 即為歐拉總計函數。如果 ${\displaystyle n}$ 為質數，那麼 ${\displaystyle \varphi (n)=n-1}$，因此，有高斯的版本[3]：

假若 ${\displaystyle p}$ 為質數，${\displaystyle a}$ 與 ${\displaystyle p}$ 互質（${\displaystyle a}$ 不是 ${\displaystyle p}$ 的倍數），那麼 ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$。

${\displaystyle \varphi (1)=1}$（小于等于1的正整数中唯一和1互質的數就是1本身）。

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

歐拉函數是積性函數，即是说若m,n互質，${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$。證明：設A, B, C是跟m, n, mn互質的數的集，據中國剩餘定理，${\displaystyle A\times B}$和${\displaystyle C}$可建立雙射(一一對應)的關係。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此${\displaystyle \varphi (n)}$的值使用算術基本定理便知，

若${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$

則${\displaystyle \varphi (n)=\prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=\prod _{p\mid n}p^{\alpha _{p}-1}(p-1)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}$。

其中${\displaystyle \alpha _{p}}$是使得${\displaystyle p^{\alpha }}$整除${\displaystyle n}$的最大整数${\displaystyle \alpha }$（这里${\displaystyle \alpha _{p_{i}}=k_{i}}$）。

例如${\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的欧拉函数${\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。也就是说：

${\displaystyle \sum _{d\mid n}\varphi (d)=n}$

其中的d为n的正约数。

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

${\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)}$

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

對任何兩個互質的正整數a, m（即 gcd(a,m) = 1），${\displaystyle m\geq 2}$，有

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}$

即欧拉定理。

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

當m是質數p時，此式則為：

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

即費馬小定理。

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

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

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}$

其中ζ(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)}$

${\displaystyle .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum _{h=1}^{\infty }\left(\sum _{fg=h}1\cdot \varphi (g)\right){\frac {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}}}}$

使用开始时的等式，就得到：${\displaystyle \sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }{\frac {h}{h^{s}}}}$

于是${\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}=\zeta (s-1)}$

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

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}$

其对于满足 |q|<1 的q收敛。

推导如下：

${\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}}$

后者等价于：

${\displaystyle \sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.}$

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

在n足够大时，有估计：

对每个 ε > 0，都有n > N(ε)使得 ${\displaystyle \,n^{1-\varepsilon }<\varphi (n)<n}$

如果考虑比值：

${\displaystyle \,\varphi (n)/n,}$

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

${\displaystyle C\,\log \log n/\log n.}$

${\displaystyle \varphi }$就平均值的意义上来说是与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趋于无穷大时，它们互质的概率趋于 ${\displaystyle 6/\pi ^{2}}$ 。一个相关的结果是比值${\displaystyle \varphi (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).}$

1. ${\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
2. ${\displaystyle \forall a\in N,\forall n\in N,\ \exists l\in N}$ 使得 ${\displaystyle [(a>1\land n>1)\rightarrow (l|\varphi (a^{n}-1)\land l\geq n)]}$
3. ${\displaystyle \forall a\in N,\forall n\in N,\ \exists l\in N}$ 使得 ${\displaystyle [(a>1\land n>6\land 4\nmid n)\rightarrow (l|\varphi (a^{n}-1)\land l\geq 2n)]}$
4. ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$
5. ${\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}n>1}$
6. ${\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)}$
7. ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor }$
8. ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\mathcal {O}}(n)}$
9. ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\mathcal {O}}(\log(n))}$

1. ${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}}$，其中n > 2，γ 为欧拉-马歇罗尼常数。
2. ${\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}$ ，其中n > 0。
3. 对整数n > 6，${\displaystyle \varphi (n)\geq {\sqrt {n}}}$。
4. 当n为质数时，显然有${\displaystyle \varphi (n)=n-1}$。对于合数的n，则有：

${\displaystyle \varphi (n)\leq n-{\sqrt {n}}}$

• 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页.

• Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311. 页面存档备份，存于

• 柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001

1. . [2014-10-16]. （原始内容存档于2014-10-12）.
2. Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608
3. Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814