2.6　默比乌斯函数

默比乌斯函数由德国数学家默比乌斯（August Ferdinand Möbius）提出。在数论中，经常出现像欧拉函数这种定义在正整数集上的实值或负值函数，这类函数称为数论函数。当，且和互素时，有。具有这种性质的数论函数称为积性函数（Multiplicative Function）。下面将介绍另外一个重要的积性函数，即默比乌斯函数。

定义2.6.1　默比乌斯函数(Möbius Function)

默比乌斯函数[9]:

根据默比乌斯函数计算可得前15个值，如表2-5所示。

例2.6.1　通过例子来解释一下默比乌斯函数是如何运算的。，由相同的素数所得，所以。也包含相同素数，所以。而,由不同素数所得，所以是。

 1  def isPrime(n) :
 2      if (n < 2) :
 3          return False
 4      for i in range(2, n + 1) :
 5          if (i * i <= n and n % i == 0) :
 6              return False
 7      return True
 8
 9  def mobius(N) :
10      if (N == 1) :return 1
11      p = 0
12      for i in range(1, N + 1) :
13          if (N % i == 0 and isPrime(i)) :
14              if (N % (i * i) == 0) : return 0
15              else : p = p + 1
16      if(p % 2 != 0) : return -1
17      else : return 1

定理2.6.1　默比乌斯函数的积性性质

假设和没有公因数。进一步假设是个不同素数的乘积，是个不同素数的乘积。那么就是个不同素数的乘积，即:

由定理2.6.1可知，；，由于满足素数的平方能整除360 ，因此。

那么欧拉函数与有什么关系呢？它们之间的关系可以表示为：

其中为默比乌斯函数的和函数，且，记作：

例2.6.2　假设整数，则，，，那么:

●

●

●

●

例如，，根据式(2-44)，很容易可以算出: