数学课堂
挑战≈ 16 分钟未开始

欧拉函数

核心概念

欧拉函数 φ(n)\varphi(n):11 到 nn 中与 nn 互质的正整数的个数。

计算公式:

  • 质数:φ(p)=p−1\varphi(p) = p - 1;
  • 质数的幂:φ(pk)=pk−pk−1=pk−1(p−1)\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1);
  • 积性:若 gcd⁡(m,n)=1\gcd(m,n)=1,则 φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n);
  • 通用公式:设 n=p1a1⋯pkakn = p_1^{a_1}\cdots p_k^{a_k},则
φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk).\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right).

直观理解 · 动手试试

φ(n)\varphi(n) 数的是"在 1∼n1\sim n 里有多少个数和 nn 没有公共质因数"。通用公式的来历很直观:从 nn 个数出发,每出现一个质因数 pp,就要剔除其中 1p\frac1p 比例的倍数,于是乘上 (1−1p)(1-\frac1p)。各质因数互不干扰地相乘,就得到了公式。

这个函数是数论的核心工具之一:它衡量"模 nn 意义下可逆元素的个数",直接支撑下一节的欧拉定理。先把它的计算练熟——关键就是先分解质因数,再套乘积公式。

欧拉函数

1 ~ 12 中与 12 互质的数

123456789101112
与 12 互质的(绿色)共 4 个,即 φ(12) = 4
12

φ(n) 数的是和 n 没有公共质因数的数。先分解质因数,再用公式 φ(n)=n∏(1−1/p) 即可快速算出。

例题 1用乘积公式计算

求 φ(12)\varphi(12)。

▸查看解答步骤

答: φ(12)=4

例题 2质数幂

求 φ(27)\varphi(27)。

▸查看解答步骤

答: φ(27)=18

即时练习

φ(7)\varphi(7) 等于多少?

77 是质数,φ(7)=7−1=6\varphi(7)=7-1=6。

φ(10)\varphi(10) 等于多少?

10=2×510=2\times5,φ=10⋅12⋅45=4\varphi=10\cdot\frac12\cdot\frac45=4(即 1,3,7,91,3,7,9)。

φ(9)\varphi(9) 等于多少?

9=329=3^2,φ=9−3=6\varphi=9-3=6。

φ(15)\varphi(15) 等于多少?

15=3×515=3\times5,φ=φ(3)φ(5)=2×4=8\varphi=\varphi(3)\varphi(5)=2\times4=8。

φ(32)\varphi(32) 等于多少?

32=2532=2^5,φ=25−24=32−16=16\varphi=2^5-2^4=32-16=16。

易错点

  • 直接用 n−1n-1。 只有 nn 为质数时 φ(n)=n−1\varphi(n)=n-1;合数要用乘积公式。
  • 积性条件漏掉互质。 φ(mn)=φ(m)φ(n)\varphi(mn)=\varphi(m)\varphi(n) 仅当 gcd⁡(m,n)=1\gcd(m,n)=1 才成立。
  • 质数幂公式记错。 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1},减的是 pk−1p^{k-1},不是 pp 或 11。

下一步

前置知识点
—
接下来学习