2.5　欧拉函数

欧拉函数是数论中最重要也是最基础的一个函数 ^[9] 。它以著名的数学家莱昂哈德·保罗·欧拉（Leonhard Paul Euler）的名字命名，以表彰他在数论领域做出的贡献。欧拉函数也称欧拉总计函数 (Euler’s Totient Function) 或欧拉 Phi 函数 (Euler’s Phi Function)。欧拉函数的定义如下。

定义2.5.1　欧拉函数 (Euler’s Function)

欧拉函数 是计算在封闭区间 内与 没有公因数的整数的个数。或者说是计算 内的正整数中与 互素的数目。也就是说：

注：部分参考书籍也常使用 表示欧拉函数， 是 的另一种书写形式。由于 还常常表示角度，因此本书采用 表示欧拉函数。

如果 是一个合数，则 有一个因子 ，满足 ，在 中至少有两个整数不与 互素。那么 。当 时， 。因此如果 是一个素数，那么：

反过来也成立：如果 ，且 ，那么 是一个素数。

如果 且 是一个素数，那么还可以推出：

定理2.5.1　欧拉函数的幂分解 (Prime Factorization)

如果 是一个正整数，则可以被质因数分解成：

欧拉函数进一步表示为：

例 2.5.1 计算 。

解： 根据算术基本定理，每个大于 1 的正整数都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。因此 360 可以写成：

代入式 中：

计算欧拉函数的 Python 代码如下：

 1  # 计算欧拉函数值
 2  def gcd(a, b):
 3      if(b == 0):
 4          return abs(a)
 5      else:
 6          return gcd(b, a % b)
 7  
 8  def is_coprime(a, b):
 9      return gcd(a, b) == 1
10  
11  def phi(x):
12      if x == 1:
13          return 1
14      else:
15          n = [y for y in range(1,x) if is_coprime(x,y)]
16          return len(n)
17  print(phi(360))

例 2.5.2 根据欧拉函数计算可得前 15 个欧拉函数值，如表 2-4 所示。

定理2.5.2　欧拉函数的积性性质 (Multiplicative)

如果 为正整数，使得 ，则：

证明

假设两个数 互素，则意味着 与 没有相同的质因子。设 有 个质因子， 有 个质因子，则：

假设一个整数 由素数 进行乘积运算得来，那么很容易可以得到：

例 2.5.3 计算 。

解： c2ONDYDv9RCfZ4zY8VbnTTC1bZ5s8UBrlu2M9qT4/efgWN3KcStuqJ78sM110Vve