在数论中,欧拉函数是很重要的一个函数,此函数以欧拉本人的名字命名,又称为φ函数、欧拉商数。


对于一个正整数 n,小于 n且和 n互质的正整数(包括1)的个数,记作 φ(n)。其中 φ(1)被定义为1,但是并没有任何实质的意义。

例如整数8,小于8且和8互质的正整数有:1、3、5、7,因此
φ(8) = 4。

那么欧拉函数的计算公式是什么,这里将分不同情境给出具体公式。

在此之前先引入一个概念,完全余数集合


定义小于 n且和 n互质的数构成的集合为 Zn,称呼这个集合为 n的完全余数集合。显然 |Zn| = φ(n)。

  • 对于素数 p,φ(p) = p -1
  • 很明显,素数 p和小于它的正整数均互质,而小于 p的正整数有 p-1个。
    这里用反证法
    假设 q < p,且 p和 q不互质 则 p和 q存在公约数为r,r > 1
    那么 p = kr
    这和p是素数矛盾,因此原公式成立。

  • 对于素数 p,φ(pk) = pk - pk-1
  • 小于 pk的正整数一共有 pk - 1个
    而和 pk不互质的正整数集合为:
    {1p,2p,3p,···, mp},共有m个
    而mp = pk - p
    导出m = pk-1 - 1
    因此欧拉函数的值为
    所有小于 pk的个数减去和 pk不互质的正整数个数
    φ(pk) = pk - 1 - m
    φ(pk) = pk - 1 - (pk-1 - 1)
    φ(pk) = pk - pk-1

  • 两个互质正整数 p q,φ(pq) = φ(p)φ(q)
  • 因为 n = pq, gcd(p,q) = 1
    根据中国余数定理,有
    Zn 和 Zp × Zq 之间存在一一映射
    所以 n的完全余数集合的元素个数等于集合 Zp与 Zq的元素个数乘积。
    即φ(pq) = φ(p)φ(q)


    当n为奇数时,φ(2n) = φ(2) φ(n) = φ(n)。
  • 任意正整数n
  • 根据以上的知识,我们可以得到对于任意一个正整数 n的欧拉函数。

    任意正整数 n可以表示成:
    n = p1k1 p2k2 ··· pi-1ki-1 piki
    这里p1,p2,···,pi为互质的素数

    那么
    n = p1k1 (p2k2 ··· pi-1ki-1 piki
    p1k1 和 p2k2 ··· pi-1ki-1 piki互质

    根据定理两个互质正整数 p q,φ(pq) = φ(p)φ(q)得到
    φ(n) = φ(p1k1) φ(p2k2 ··· pi-1ki-1 piki

    同理,继续分解
    φ(n) = φ(p1k1) φ(p2k2) ··· φ(pi-1ki-1) φ(piki

    得到
    φ(n) = (p1k1 - p1k1-1)(p2k2 - p2k2-1)···(pi-1ki-1 - pi-1ki-1-1)(piki - piki-1

    φ(n) = p1k1(1 - 1 / p1)p2k2(1 - 1 / p2)··· pi-1ki-1(1 - 1 / pi-1) piki(1 - 1 / pi

    φ(n) = n (1 - 1 / p1)(1 - 1 / p2)···(1 - 1 / pi-1)(1 - 1 / pi

    至此,欧拉函数证毕。