欧拉定理是数论中的一项基本结果,描述了模算术中整数幂的性质。该定理指出,若 n≥2 为整数,且整数 a 与 n 互素,则
aφ(n)≡1(modn),
其中,φ(n) 为欧拉函数,表示从 1 到 n 的整数中与 n 互素的整数个数。该定理以莱昂哈德·欧拉的名字命名,是费马小定理的推广,为化简大指数、计算模逆元以及理解RSA密码的代数原理提供了基础。
定理表述与术语
两个整数的最大公约数为 1 时,称它们互素。因此,欧拉定理的前提是
gcd(a,n)=1.
结论 aφ(n)≡1(modn) 表示 n 整除 aφ(n)−1。等价地说,aφ(n) 除以 n 的余数为 1。
欧拉函数定义为
φ(n)=#{k:1≤k≤n, gcd(k,n)=1}.
若 n 的不同素因子为 p1,…,pr,则
φ(n)=ni=1∏r(1−pi1).
特别地,对于素数 p 和整数 k≥1,有
φ(p)=p−1,φ(pk)=pk−1(p−1).
例如,1 到 10 之间与 10 互素的整数为 1,3,7,9,因此 φ(10)=4。由于 3 与 10 互素,根据欧拉定理,
34=81≡1(mod10).
互素这一限制条件不可缺少。若 gcd(a,n)>1,则 a 与 n 的某个公共素因子会整除 a 的每个正整数次幂,因此这些幂都不可能模 n 同余于 1。
初等证明
模 n 的简化剩余系由所有与 n 互素的同余类各取一个代表元组成。将这样的一个剩余系记为
r1,r2,…,rφ(n).
若 gcd(a,n)=1,则乘以 a 只会使这些同余类重新排列。事实上,每个 ari 仍与 n 互素,且由
ari≡arj(modn)
可得
ri≡rj(modn),
因为与模数互素的因子可以约去。因此,乘以 a 在这些简化剩余类上诱导了一个置换。
于是,它们的乘积满足
(ar1)(ar2)⋯(arφ(n))≡r1r2⋯rφ(n)(modn).
提取 a 的幂,得到
aφ(n)r1r2⋯rφ(n)≡r1r2⋯rφ(n)(modn).
乘积 r1r2⋯rφ(n) 与 n 互素,因此也可以约去,从而得到
aφ(n)≡1(modn).
这里能否约去因子,取决于该因子是否与模数互素,而不只是它是否非零。对于合数模数,这一区别至关重要。
群论解释
在群论中,模 n 的可逆剩余类在乘法运算下构成一个群,记为
(Z/nZ)×.
它是环(数学) Z/nZ 的单位群,恰有 φ(n) 个元素。
根据拉格朗日定理(群论),有限群中任一元素的阶都整除群的元素个数。因此,将 (Z/nZ)× 中任一元素取 φ(n) 次幂,都会得到单位元。这正是欧拉定理。
更具体地说,a 模 n 的乘法阶记为 ordn(a),是满足
ad≡1(modn).
的最小正整数 d。当 gcd(a,n)=1 时,
ordn(a)∣φ(n).
因此,欧拉定理给出了适用于所有可逆剩余类的通用指数,但它不一定是某个特定剩余类所对应的最小指数。
与费马小定理的关系
当模数为素数 p 时,每个非零剩余类都可逆,且 φ(p)=p−1。欧拉定理变为
ap−1≡1(modp)if p∤a,
这就是费马小定理。
与之等价的素数模数表述
ap≡a(modp)
对任意整数 a 都成立,包括 p 的倍数。
欧拉的贡献在于,用 φ(n) 代替 p−1,并加上互素条件,从而将素数模数下的结果推广到任意正整数模数。这一定理是欧拉在18世纪发展数论的成果之一;其现代群论表述则将它纳入了更一般的有限群理论。
应用
化简大指数
若 gcd(a,n)=1,将非负整数指数 m 写成
m=qφ(n)+r,0≤r<φ(n).
则
am=(aφ(n))qar≡ar(modn).
例如,φ(20)=8,且 gcd(7,20)=1。由于
123≡3(mod8),
可得
7123≡73=343≡3(mod20).
如果底数与 n 不互素,通常不能用这种方式将指数对 φ(n) 取模。
计算模逆元
a 模 n 的模乘法逆元是满足
ab≡1(modn).
的整数 b。这样的逆元存在,当且仅当 gcd(a,n)=1。由欧拉定理可得
a−1≡aφ(n)−1(modn).
例如,由于 φ(10)=4,
3−1≡33=27≡7(mod10).
这个公式在理论研究和已知欧拉函数值的情况下很有用。扩展欧几里得算法也能计算模逆元,而且不需要知道 φ(n)。
RSA密码
欧拉定理是解释RSA密码系统数学原理的核心。对于不同的素数 p 和 q,令
n=pq,φ(n)=(p−1)(q−1).
若正整数 e 和 d 满足
ed≡1(modφ(n)),
则对于每个与 n 互素的消息代表值 m,都有
(me)d=med≡m(modn).
对于与 n 不互素的消息代表值,RSA也能正确还原消息,但仅凭欧拉定理无法证明这种情况。分别在模 p 和模 q 下应用费马小定理,再利用中国剩余定理,即可证明该结果对模 n 的每个剩余类都成立。
这种代数上的正确性与密码学安全性并不相同;安全的加密方案除了直接进行模幂运算外,还需要其他构造。
更小的指数与局限性
卡迈克尔函数 λ(n) 是使每个与 n 互素的整数 a 都满足
aλ(n)≡1(modn)
的最小正整数。它满足
λ(n)∣φ(n).
因此,它给出的通用指数可能比欧拉函数值更小。
例如,
φ(8)=4,λ(8)=2.
每个奇数都满足 a2≡1(mod8),所以欧拉定理给出的指数 4 虽然有效,却不是最小的。对于某个特定底数,其乘法阶还可能更小。
欧拉定理也不是素性判定准则:只要满足前提条件,并使用正确的欧拉函数值,其结论对任何模数都成立。相比之下,费马型素性检验所用的同余式 an−1≡1(modn),即使在 n 为合数时也可能成立。
最后,这一定理本身并未提供一种对任意大整数高效计算 φ(n) 的方法。已知素因数分解时,利用乘积公式计算很直接,但求出素因数分解在计算上可能很困难。对于RSA模数 n=pq,知道 φ(n) 就能得到
p+q=n+1−φ(n),
进而可将 p 和 q 作为方程
x2−(n+1−φ(n))x+n=0.
的两个根求出。