欧拉函数(Euler’s totient function),也称为欧拉的 函数(phi 函数),是一个在数论中使用的函数,用来计算小于或等于给定整数 且与 互质的正整数的个数。它用希腊字母 表示,可以记作 。换句话说,它表示在范围 内,与 的最大公因数 等于 的整数 的个数。这些满足条件的整数 有时被称为 的互质数。

例如,对于 ,满足条件的互质数有 个,分别是 。它们都与 互质,但在这个范围内的另外三个数 不满足条件,因为 。因此,。再举一个例子,,因为对于 ,范围内的唯一整数是 本身,且

欧拉函数是一个乘性函数,意味着如果两个数 互质,那么 。这个函数给出了模 的整数乘法群(即环 的单位群)的阶数。它还用于定义 RSA 加密系统。

欧拉在 1763 年引入了这个函数,但当时他没有选择任何特定的符号来表示它。在 1784 年的一篇论文中,欧拉进一步研究了这个函数,并选择了希腊字母 来表示它:他用 表示“小于 且与 没有公约数的数的数量”。这个定义在 时与当前的欧拉函数定义不同,但在其他情况下是相同的。现在标准的符号 来自高斯 1801 年的著作《算术研究》,尽管高斯没有在参数周围使用括号,而是写作 。因此,它经常被称为欧拉的 函数或简称为 函数。

计算欧拉函数有几个公式可用。

  1. 欧拉的乘积公式:,其中乘积是对 的不同素数因子 进行的。
  2. 欧拉函数的另一种等价形式是:,其中 的素因子分解, 是不同的素数。