Euler 函数

欧拉函数
术语名称	欧拉函数
英语名称	Euler's totient function
别名	Euler's function, 欧拉φ函数, Euler's phi function

totative
术语名称
英语名称	totative

totient
术语名称
英语名称	totient

cototient
术语名称
英语名称	cototient

欧拉函数(Euler's totient function)指一个函数，把一个正整数，映射到又不大于其的又与其互质的正整数数目。

定义

Euler 函数
运算名称	Euler 函数
运算符号	[math]\displaystyle{ \varphi() }[/math],[math]\displaystyle{ \phi() }[/math]
Latex	\varphi , \phi
运算对象	正整数
运算元数	1
运算结果
定义域	[math]\displaystyle{ \mathbb{N}^* }[/math]
陪域	[math]\displaystyle{ \mathbb{N}^* }[/math]

对正整数 [math]\displaystyle{ n }[/math] ，称任意不大于 [math]\displaystyle{ n }[/math] 且与 [math]\displaystyle{ n }[/math] 互质的正整数称为正整数 [math]\displaystyle{ n }[/math] 的一个 totative ，正整数 [math]\displaystyle{ n }[/math] 的 totative 的个数称为正整数 [math]\displaystyle{ n }[/math] 的 totient ，将不大于 [math]\displaystyle{ n }[/math] 的其他正整数数目称为正整数 [math]\displaystyle{ n }[/math] 的 cototient 。

对正整数 [math]\displaystyle{ n }[/math] ，记函数将任意正整数 [math]\displaystyle{ n }[/math] 映射到 [math]\displaystyle{ n }[/math] 的 totient ，称为欧拉函数(Euler's totient function)，记作 [math]\displaystyle{ \varphi(n) }[/math] ，也有时记作 [math]\displaystyle{ \phi(x) }[/math] 。

性质

Euler 函数是一个乘性函数。
可依次按 [math]\displaystyle{ p_i }[/math] 、 [math]\displaystyle{ p_i^k }[/math] 、 [math]\displaystyle{ n = \prod p_i^{n_i} }[/math] 顺序推断出以下结果。

将正整数 [math]\displaystyle{ n }[/math] 写成其标准分解式，如下：

[math]\displaystyle{ n = \prod_{p_i \mid n} p_i^{n_i} = p_1^{n_1} p_2^{n_2} \dots p_k^{n_k} }[/math]

其中 [math]\displaystyle{ p_i }[/math] 是互不相同的质因数。则有

[math]\displaystyle{ \varphi(n) = n \prod_{p_i \mid n} \left( 1 - \tfrac{1}{p_i} \right) = n \left( 1 - \tfrac{1}{p_1} \right) \left( 1 - \tfrac{1}{p_2} \right) \dots \left( 1 - \tfrac{1}{p_k} \right) }[/math]

等价地，可以写成

[math]\displaystyle{ \varphi(n) = \prod_{p_i \mid n} p_i^{ n_i - 1 } \left( p_i - 1 \right) = p_1^{n_1-1} \left( p_1 - 1 \right) p_2^{n_2-1} \left( p_2 - 1 \right) \dots p_k^{n_k-1} \left( p_k - 1 \right) }[/math]

有 [math]\displaystyle{ \sum_{d\mid n} \varphi(d) = \sum_{d\mid n} \varphi(n/d) = n }[/math] 。

也就是说， Euler 函数的 Möbius 变换是恒等函数 [math]\displaystyle{ n }[/math] 。

数论函数
分类	加性函数	完全加性函数
分类	乘性函数	完全乘性函数
性质	Möbius 反演（Möbius 变换、 Möbius 逆变换）
性质	Dirichlet 卷积
常见数论函数
除数函数 [math]\displaystyle{ \sigma_k(n) }[/math]	除数函数 [math]\displaystyle{ \sigma_0(n) }[/math]/[math]\displaystyle{ \tau(n) }[/math]/[math]\displaystyle{ d(n) }[/math]	除数和函数 [math]\displaystyle{ \sigma_1(n) }[/math]/[math]\displaystyle{ \sigma(n) }[/math]
Euler 函数	Euler 函数 [math]\displaystyle{ \varphi(n) }[/math]	Carmichael 函数 [math]\displaystyle{ \lambda(n) }[/math]
二次剩余相关符号	Legendre 符号 [math]\displaystyle{ (\tfrac{n}{p}) }[/math]	Jacobi 符号 [math]\displaystyle{ (\tfrac{n}{d}) }[/math]
乘法阶数与指标	乘法阶数 [math]\displaystyle{ \operatorname{ord}_{m} n }[/math]/[math]\displaystyle{ \delta_{m}(n) }[/math]	指标 [math]\displaystyle{ \operatorname{ind}_{g} n }[/math]/[math]\displaystyle{ \gamma_{m,g}(n) }[/math]
其他	相异质因子个数函数 [math]\displaystyle{ \omega(n) }[/math]	质因子个数函数 [math]\displaystyle{ \Omega(n) }[/math]、Liouville 函数 [math]\displaystyle{ \lambda(n) }[/math]
	质数计数函数 [math]\displaystyle{ \pi(n) }[/math]	Чебышёв 第一函数 [math]\displaystyle{ \theta(n) }[/math]、第二函数 [math]\displaystyle{ \psi(n) }[/math]、Mangoldt 函数 [math]\displaystyle{ \Lambda(n) }[/math]
	Möbius 函数 [math]\displaystyle{ \mu(n) }[/math]
	Dirichlet 特征 [math]\displaystyle{ \chi(n;m) }[/math]

琐事

命名

单词 totient 有时被译为“欧拉商”或“欧拉商数”，但这个词字面含义上不正确，且很不常用，故未列出。

数列编号

A000010