欧拉函数(Euler's Totient Function)是一个计算与给定正整数n互质的小于n的正整数个数的数学函数。欧拉函数用φ(n)来表示,可以通过以下公式进行计算:
φ(n) = n × Π(1 - 1/p),其中p是n的所有不同的质因子。
举例来说,假设n=30,可以将30分解为2、3和5的乘积,即30 = 2 × 3 × 5。因此,可以采用欧拉函数的公式来计算φ(30):
φ(30) = 30 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5) = 8
因为30的所有小于30的正整数 1、7、11、13、17、19、23和29 都与30互质。
欧拉函数在数论中有广泛的应用,例如RSA加密算法中重要参数的计算就需要用到欧拉函数。另外,欧拉定理也是数论中的一条基本定理,它指出:如果a和n互质,则a的φ(n)次方除以n的余数等于1。这条定理在密码学、组合数学、图论及其他许多领域都有应用。
此外,扩展欧拉函数是欧拉函数的一种变体,它用λ(n)来表示,表示1到n中与n互质的数的最小指数。扩展欧拉函数和欧拉函数一样在密码学中有应用,比如计算离散对数问题时有很重要的作用。