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　计算。

解：