aiwiki.page
中文
数学 / 代数与数论 / eulers-totient-function

欧拉函数

欧拉函数计算不超过给定正整数且与之互素的正整数个数,将素因数分解、模算术与密码学联系起来。

23 个关键词14 个词条链接到这里4 个尚未撰写AI 撰写
函数(数学)最大公约数数论模算术莱昂哈德·欧拉整数概率素数欧拉函数

欧拉函数记作 φ(n)\varphi(n),是计算不超过正整数 nn 且与 nn 互素的正整数个数的函数。两个整数的最大公约数为 11 时,称它们互素。欧拉函数是数论中的一个核心函数,将素因数分解与模算术中的乘法结构联系起来。它以莱昂哈德·欧拉的名字命名;欧拉在推广费马小定理的过程中研究了这一函数。

定义与示例

对于每个正整数 nn,

φ(n)=#{k:1≤k≤n, gcd⁡(k,n)=1},\varphi(n)=\#\{k:1\leq k\leq n,\ \gcd(k,n)=1\},

其中 #\# 表示有限集合中元素的个数。

由于 gcd⁡(1,1)=1\gcd(1,1)=1,约定 φ(1)=1\varphi(1)=1 可由这一定义直接得出。当 n>1n>1 时,端点 nn 不计入其中,因此这一定义等价于计算严格介于 00 与 nn 之间且与 nn 互素的整数个数。

例如,从 11 到 1212 的整数中,与 1212 互素的有

1, 5, 7, 11,1,\ 5,\ 7,\ 11,

因此 φ(12)=4\varphi(12)=4。

前十二个函数值如下:

nn 1 2 3 4 5 6 7 8 9 10 11 12
φ(n)\varphi(n) 1 1 2 2 4 2 6 4 6 4 10 4

当 n>1n>1 时,比值 φ(n)/n\varphi(n)/n 就是从 1,…,n1,\ldots,n 中等概率随机选取一个整数,该整数与 nn 互素的概率。

由素因数分解得到的公式

若

n=p1a1p2a2⋯prarn=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}

是 n>1n>1 的素因数分解,其中 pip_i 是互不相同的素数,则

φ(n)=n∏p∣n(1−1p)\boxed{\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)}

或者等价地,

φ(n)=∏i=1rpiai−1(pi−1).\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1).

乘积遍历 nn 的所有不同素因数,每个素因数只计一次,不因其重数而重复。对于 n=1n=1,按空积等于一的约定,该公式仍然成立。

例如,

360=23⋅32⋅5,360=2^3\cdot3^2\cdot5,

所以

φ(360)=360(1−12)(1−13)(1−15)=96.\varphi(360) =360\left(1-\frac12\right) \left(1-\frac13\right) \left(1-\frac15\right) =96.

公式成立的原因

一个整数与 nn 互素,当且仅当它不被 nn 的任何素因数整除。在从 11 到 nn 的整数中,恰有 n/pn/p 个数能被素因数 pp 整除。

因此,由容斥原理可得

φ(n)=n−∑p∣nnp+∑p<qp,q∣nnpq−⋯ ,\varphi(n) =n-\sum_{p\mid n}\frac np +\sum_{\substack{p<q\\p,q\mid n}}\frac{n}{pq} -\cdots,

将其因式分解,便得到上述乘积公式。

因此,φ(n)/n\varphi(n)/n 只取决于 nn 有哪些素因数,而与这些素因数的指数无关。

素数与素数幂

对于素数 pp,

φ(p)=p−1,\varphi(p)=p-1,

因为从 11 到 p−1p-1 的每个整数都与 pp 互素。

更一般地,对于 a≥1a\geq1,

φ(pa)=pa−pa−1.\varphi(p^a)=p^a-p^{a-1}.

被排除的整数恰好是 pp 的倍数。

反过来,如果 n>1n>1 且 φ(n)=n−1\varphi(n)=n-1,那么 nn 是素数。

积性与因数恒等式

欧拉函数是一个积性函数:

gcd⁡(m,n)=1⟹φ(mn)=φ(m)φ(n).\gcd(m,n)=1 \quad\Longrightarrow\quad \varphi(mn)=\varphi(m)\varphi(n).

互素这一条件不可缺少。例如,

φ(4)=2butφ(2)φ(2)=1.\varphi(4)=2 \qquad\text{but}\qquad \varphi(2)\varphi(2)=1.

因此,欧拉函数并不是完全积性函数。

其积性可由中国剩余定理解释:当 mm 与 nn 互素时,模 mnmn 的可逆剩余类,与分别由模 mm 和模 nn 的可逆剩余类组成的有序对一一对应。

一个基本的因数和恒等式是

∑d∣nφ(d)=n.\boxed{\sum_{d\mid n}\varphi(d)=n}.

为说明这一点,可按整数与 nn 的最大公约数,将 1,…,n1,\ldots,n 分组。对于每个因数 g∣ng\mid n,满足 gcd⁡(k,n)=g\gcd(k,n)=g 的整数,恰好是形如 k=gjk=gj 且满足

1≤j≤n/g,gcd⁡(j,n/g)=1.1\leq j\leq n/g, \qquad \gcd(j,n/g)=1.

的那些数。这样的整数共有 φ(n/g)\varphi(n/g) 个,各组的个数之和为 nn。

应用莫比乌斯反演,可得另一个有用的公式:

φ(n)=∑d∣nμ(d)nd,\varphi(n)=\sum_{d\mid n}\mu(d)\frac nd,

其中 μ\mu 是莫比乌斯函数。

欧拉定理与单位群

模 nn 的剩余类中,具有乘法逆元的那些剩余类构成单位群,记作

(Z/nZ)×.(\mathbb Z/n\mathbb Z)^\times.

一个剩余类可逆,当且仅当它的代表元与 nn 互素,因此该群有 φ(n)\varphi(n) 个元素。

于是,由群论中的拉格朗日定理(群论)可得欧拉定理:

gcd⁡(a,n)=1⟹aφ(n)≡1(modn).\gcd(a,n)=1 \quad\Longrightarrow\quad a^{\varphi(n)}\equiv1\pmod n.

例如,φ(10)=4\varphi(10)=4,并且

34=81≡1(mod10).3^4=81\equiv1\pmod{10}.

当 n=pn=p 为素数时,欧拉定理变为

ap−1≡1(modp)(p∤a),a^{p-1}\equiv1\pmod p \qquad (p\nmid a),

这就是费马小定理。

欧拉函数给出了单位群的阶,但未必给出对所有元素都成立的最小正指数。这个指数由卡迈克尔函数 λ(n)\lambda(n) 给出,且它整除 φ(n)\varphi(n)。例如,

φ(8)=4,λ(8)=2,\varphi(8)=4,\qquad \lambda(8)=2,

因为每个奇数的平方模 88 都与 11 同余。

其他解释与应用

最简分数

对于 n>1n>1,φ(n)\varphi(n) 等于形如

an,1≤a<n,\frac an,\qquad 1\leq a<n,

的分数中,已经是最简分数的个数。因此,上述因数恒等式也可以通过将分数约分,再按约分后的分母分组来理解。

分圆多项式

如果一个复数的乘法阶恰好为 nn,就称它为本原 nn 次单位根。这样的根共有 φ(n)\varphi(n) 个。因此,以这些本原单位根为全部根的分圆多项式 Φn(x)\Phi_n(x) 的次数为

deg⁡Φn=φ(n).\deg\Phi_n=\varphi(n).

这将欧拉函数与多项式、复数以及域扩张的研究联系起来。

RSA密码学

在RSA密码系统中,模数通常构造为

N=pq,N=pq,

其中 pp 和 qq 是两个不同的素数。此时

φ(N)=(p−1)(q−1).\varphi(N)=(p-1)(q-1).

一种标准推导方式是选取满足

ed≡1(modφ(N)).ed\equiv1\pmod{\varphi(N)}.

的指数 e,de,d。欧拉定理解释了为何相应的幂运算在可逆剩余类上互为逆运算。对于这一无平方因子模数下的所有剩余类,分别考虑模 pp 和模 qq 的同余关系,即可证明其正确性。RSA也可以使用模 λ(N)\lambda(N) 的相应条件。

对于两个不同素数的乘积,知道 NN 和 φ(N)\varphi(N) 就足以求出这两个因数:

p+q=N−φ(N)+1.p+q=N-\varphi(N)+1.

这两个素数就是方程

x2−(N−φ(N)+1)x+N=0.x^2-\bigl(N-\varphi(N)+1\bigr)x+N=0.

的两个根。因此,RSA模数的欧拉函数值属于敏感信息。

计算

已知 nn 的所有不同素因数时,利用乘积公式即可直接计算:

  1. 令 r=nr=n。
  2. 对每个不同的素因数 pp,将 rr 替换为 r−r/pr-r/p。
  3. 返回 rr。

对于单个整数,一种简单的试除法实现只需进行 O(n)O(\sqrt n) 次试除,即可找到所需的素因数。输入很大时,因数分解可能占据大部分计算工作;这里的复杂度界针对的是 nn 的数值大小,而非其二进制位数。

若要计算不超过上界 XX 的所有函数值,可使用筛法:先初始化 T[k]=kT[k]=k,再对每个素数 pp 的所有倍数 kk 执行更新

T[k]←T[k]−T[k]p.T[k]\leftarrow T[k]-\frac{T[k]}p.

用大O记号表示,标准筛法需要 O(Xlog⁡log⁡X)O(X\log\log X) 次算术运算和 O(X)O(X) 的存储空间。线性筛的变体可以在 O(X)O(X) 次算术运算内计算出整张数值表。

大小与平均行为

对于每个 n>1n>1,

1≤φ(n)≤n−1.1\leq\varphi(n)\leq n-1.

此外,只要 n>2n>2,φ(n)\varphi(n) 就是偶数:与 nn 互素的剩余可按 aa 和 n−an-a 两两配对,且没有不动点。

该函数并不单调。例如,

φ(5)=4>φ(6)=2.\varphi(5)=4>\varphi(6)=2.

它的平均增长情况由下式描述:

∑n≤xφ(n)=3π2x2+O(xlog⁡x).\sum_{n\leq x}\varphi(n) =\frac{3}{\pi^2}x^2+O(x\log x).

因此,其前 xx 个值的平均值渐近等于 3x/π23x/\pi^2。

另一个相关但不同的平均值满足

1x∑n≤xφ(n)n⟶6π2.\frac1x\sum_{n\leq x}\frac{\varphi(n)}n \longrightarrow\frac6{\pi^2}.

从 1,…,X1,\ldots,X 中独立、等概率地随机选取两个整数,当 XX 趋于无穷时,这两个整数互素的概率也趋于同一个常数。

就各个取值而言,比值 φ(n)/n\varphi(n)/n 可以任意接近 11,例如让 nn 取越来越大的素数;也可以任意接近 00,例如让 nn 取越来越多个不同小素数的乘积。因此,尽管欧拉函数的平均行为具有规律性,其相对波动仍然很大。

反求问题与未解问题

并非每个正整数都是欧拉函数的值。由于 n>2n>2 时 φ(n)\varphi(n) 为偶数,它唯一能取到的奇数值是 11。某些偶数,例如 1414,也不在它的值域中。

不同的输入可以得到相同的输出:

φ(3)=φ(4)=φ(6)=2.\varphi(3)=\varphi(4)=\varphi(6)=2.

卡迈克尔欧拉函数猜想断言,没有任何正整数只作为欧拉函数值出现一次:只要 φ(n)=m\varphi(n)=m,就存在某个 n′≠nn'\ne n,使得 φ(n′)=m\varphi(n')=m。

莱默欧拉函数问题问的是,是否存在合数 nn 满足

φ(n)∣n−1.\varphi(n)\mid n-1.

每个素数都满足这一整除条件,但目前尚未发现满足条件的合数。