欧拉函数记作 φ(n),是计算不超过正整数 n 且与 n 互素的正整数个数的函数。两个整数的最大公约数为 1 时,称它们互素。欧拉函数是数论中的一个核心函数,将素因数分解与模算术中的乘法结构联系起来。它以莱昂哈德·欧拉的名字命名;欧拉在推广费马小定理的过程中研究了这一函数。
定义与示例
对于每个正整数 n,
φ(n)=#{k:1≤k≤n, gcd(k,n)=1},
其中 # 表示有限集合中元素的个数。
由于 gcd(1,1)=1,约定 φ(1)=1 可由这一定义直接得出。当 n>1 时,端点 n 不计入其中,因此这一定义等价于计算严格介于 0 与 n 之间且与 n 互素的整数个数。
例如,从 1 到 12 的整数中,与 12 互素的有
1, 5, 7, 11,
因此 φ(12)=4。
前十二个函数值如下:
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| φ(n) |
1 |
1 |
2 |
2 |
4 |
2 |
6 |
4 |
6 |
4 |
10 |
4 |
当 n>1 时,比值 φ(n)/n 就是从 1,…,n 中等概率随机选取一个整数,该整数与 n 互素的概率。
由素因数分解得到的公式
若
n=p1a1p2a2⋯prar
是 n>1 的素因数分解,其中 pi 是互不相同的素数,则
φ(n)=np∣n∏(1−p1)
或者等价地,
φ(n)=i=1∏rpiai−1(pi−1).
乘积遍历 n 的所有不同素因数,每个素因数只计一次,不因其重数而重复。对于 n=1,按空积等于一的约定,该公式仍然成立。
例如,
360=23⋅32⋅5,
所以
φ(360)=360(1−21)(1−31)(1−51)=96.
公式成立的原因
一个整数与 n 互素,当且仅当它不被 n 的任何素因数整除。在从 1 到 n 的整数中,恰有 n/p 个数能被素因数 p 整除。
因此,由容斥原理可得
φ(n)=n−p∣n∑pn+p<qp,q∣n∑pqn−⋯,
将其因式分解,便得到上述乘积公式。
因此,φ(n)/n 只取决于 n 有哪些素因数,而与这些素因数的指数无关。
素数与素数幂
对于素数 p,
φ(p)=p−1,
因为从 1 到 p−1 的每个整数都与 p 互素。
更一般地,对于 a≥1,
φ(pa)=pa−pa−1.
被排除的整数恰好是 p 的倍数。
反过来,如果 n>1 且 φ(n)=n−1,那么 n 是素数。
积性与因数恒等式
欧拉函数是一个积性函数:
gcd(m,n)=1⟹φ(mn)=φ(m)φ(n).
互素这一条件不可缺少。例如,
φ(4)=2butφ(2)φ(2)=1.
因此,欧拉函数并不是完全积性函数。
其积性可由中国剩余定理解释:当 m 与 n 互素时,模 mn 的可逆剩余类,与分别由模 m 和模 n 的可逆剩余类组成的有序对一一对应。
一个基本的因数和恒等式是
d∣n∑φ(d)=n.
为说明这一点,可按整数与 n 的最大公约数,将 1,…,n 分组。对于每个因数 g∣n,满足 gcd(k,n)=g 的整数,恰好是形如 k=gj 且满足
1≤j≤n/g,gcd(j,n/g)=1.
的那些数。这样的整数共有 φ(n/g) 个,各组的个数之和为 n。
应用莫比乌斯反演,可得另一个有用的公式:
φ(n)=d∣n∑μ(d)dn,
其中 μ 是莫比乌斯函数。
欧拉定理与单位群
模 n 的剩余类中,具有乘法逆元的那些剩余类构成单位群,记作
(Z/nZ)×.
一个剩余类可逆,当且仅当它的代表元与 n 互素,因此该群有 φ(n) 个元素。
于是,由群论中的拉格朗日定理(群论)可得欧拉定理:
gcd(a,n)=1⟹aφ(n)≡1(modn).
例如,φ(10)=4,并且
34=81≡1(mod10).
当 n=p 为素数时,欧拉定理变为
ap−1≡1(modp)(p∤a),
这就是费马小定理。
欧拉函数给出了单位群的阶,但未必给出对所有元素都成立的最小正指数。这个指数由卡迈克尔函数 λ(n) 给出,且它整除 φ(n)。例如,
φ(8)=4,λ(8)=2,
因为每个奇数的平方模 8 都与 1 同余。
其他解释与应用
最简分数
对于 n>1,φ(n) 等于形如
na,1≤a<n,
的分数中,已经是最简分数的个数。因此,上述因数恒等式也可以通过将分数约分,再按约分后的分母分组来理解。
分圆多项式
如果一个复数的乘法阶恰好为 n,就称它为本原 n 次单位根。这样的根共有 φ(n) 个。因此,以这些本原单位根为全部根的分圆多项式 Φn(x) 的次数为
degΦn=φ(n).
这将欧拉函数与多项式、复数以及域扩张的研究联系起来。
RSA密码学
在RSA密码系统中,模数通常构造为
其中 p 和 q 是两个不同的素数。此时
φ(N)=(p−1)(q−1).
一种标准推导方式是选取满足
ed≡1(modφ(N)).
的指数 e,d。欧拉定理解释了为何相应的幂运算在可逆剩余类上互为逆运算。对于这一无平方因子模数下的所有剩余类,分别考虑模 p 和模 q 的同余关系,即可证明其正确性。RSA也可以使用模 λ(N) 的相应条件。
对于两个不同素数的乘积,知道 N 和 φ(N) 就足以求出这两个因数:
p+q=N−φ(N)+1.
这两个素数就是方程
x2−(N−φ(N)+1)x+N=0.
的两个根。因此,RSA模数的欧拉函数值属于敏感信息。
计算
已知 n 的所有不同素因数时,利用乘积公式即可直接计算:
- 令 r=n。
- 对每个不同的素因数 p,将 r 替换为 r−r/p。
- 返回 r。
对于单个整数,一种简单的试除法实现只需进行 O(n) 次试除,即可找到所需的素因数。输入很大时,因数分解可能占据大部分计算工作;这里的复杂度界针对的是 n 的数值大小,而非其二进制位数。
若要计算不超过上界 X 的所有函数值,可使用筛法:先初始化 T[k]=k,再对每个素数 p 的所有倍数 k 执行更新
T[k]←T[k]−pT[k].
用大O记号表示,标准筛法需要 O(XloglogX) 次算术运算和 O(X) 的存储空间。线性筛的变体可以在 O(X) 次算术运算内计算出整张数值表。
大小与平均行为
对于每个 n>1,
1≤φ(n)≤n−1.
此外,只要 n>2,φ(n) 就是偶数:与 n 互素的剩余可按 a 和 n−a 两两配对,且没有不动点。
该函数并不单调。例如,
φ(5)=4>φ(6)=2.
它的平均增长情况由下式描述:
n≤x∑φ(n)=π23x2+O(xlogx).
因此,其前 x 个值的平均值渐近等于 3x/π2。
另一个相关但不同的平均值满足
x1n≤x∑nφ(n)⟶π26.
从 1,…,X 中独立、等概率地随机选取两个整数,当 X 趋于无穷时,这两个整数互素的概率也趋于同一个常数。
就各个取值而言,比值 φ(n)/n 可以任意接近 1,例如让 n 取越来越大的素数;也可以任意接近 0,例如让 n 取越来越多个不同小素数的乘积。因此,尽管欧拉函数的平均行为具有规律性,其相对波动仍然很大。
反求问题与未解问题
并非每个正整数都是欧拉函数的值。由于 n>2 时 φ(n) 为偶数,它唯一能取到的奇数值是 1。某些偶数,例如 14,也不在它的值域中。
不同的输入可以得到相同的输出:
φ(3)=φ(4)=φ(6)=2.
卡迈克尔欧拉函数猜想断言,没有任何正整数只作为欧拉函数值出现一次:只要 φ(n)=m,就存在某个 n′=n,使得 φ(n′)=m。
莱默欧拉函数问题问的是,是否存在合数 n 满足
φ(n)∣n−1.
每个素数都满足这一整除条件,但目前尚未发现满足条件的合数。