bt2-L 2.6 默比乌斯函数

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

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

默比乌斯函数[9]:

pg38a

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

表2-5 前15个默比乌斯函数值

图片表格

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 ,因此

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

其中为默比乌斯函数的和函数,且,记作:

pg39a

2.6.2 假设整数,则,那么:

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