数论10_欧拉函数_phi

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王时间刺客空间掌握者倔强青铜

2026-08-23 15:02:05

发布于：广东

6阅读
0回复
0点赞

10 欧拉函数 φ(n)\varphi(n)

学习目标

学完这一节，你应该能够：

  • 理解欧拉函数 φ(n)\varphi(n) 的含义；
  • 会求素数和质数幂的欧拉函数；
  • 理解一般公式为什么只和不同的质因子有关；
  • 一步一步理解一般公式的来源；
  • 看懂求单个 φ(n)\varphi(n) 的 C++ 代码。

1. 欧拉函数的定义

欧拉函数：

φ(n)\varphi(n)

表示：

在 1,2,…,n1,2,\dots,n 中，与 nn 互质的正整数有多少个。

例如：

n=8n=8

从 1 到 8：

1,2,3,4,5,6,7,81,2,3,4,5,6,7,8

其中与 8 互质的有：

1,3,5,71,3,5,7

所以：

φ(8)=4\boxed{\varphi(8)=4}

当 n>1n>1 时，nn 本身与 nn 的最大公约数是 nn，所以它不会被计入。

2. 素数的情况

如果 pp 是素数，那么：

1,2,…,p−11,2,\dots,p-1

都与 pp 互质。

一共有：

p−1p-1

个。

因此：

φ(p)=p−1\boxed{\varphi(p)=p-1}

例如：

φ(7)=6\varphi(7)=6

3. 质数幂的情况

现在考虑：

n=pkn=p^k

其中 pp 是素数。

pkp^k 只有一个不同的质因子：

pp

所以一个整数与 pkp^k 不互质，当且仅当它也是 pp 的倍数。

从 1 到 pkp^k 中，pp 的倍数是：

p,2p,3p,…,pk−1pp,2p,3p,\dots,p^{k-1}p

一共有：

pk−1p^{k-1}

个。

所以：

φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}

也可以写成：

φ(pk)=pk(1−1p)\boxed{\varphi(p^k)=p^k\left(1-\frac1p\right)}

4. 一般的 nn 为什么只看不同的质因子

例如：

12=22×312=2^2\times3

一个整数 xx 与 12 互质，当且仅当：

  • xx 不是 2 的倍数；
  • xx 不是 3 的倍数。

这里并不需要额外要求“不能被 222^2 整除”。

因为只要 xx 能被 2 整除，它就已经和 12 拥有公共因子 2，不再互质。

因此判断是否互质时，真正重要的是：

2, 32,\ 3

这两个不同的质因子。

一般地，如果：

n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

那么一个整数与 nn 互质，当且仅当它不被任何：

p1,p2,…,pkp_1,p_2,\dots,p_k

整除。

5. 先看只有两个不同质因子的情况

假设：

n=paqbn=p^aq^b

其中 p,qp,q 是不同的素数。

从 1 到 nn 一共有：

nn

个整数。

其中 pp 的倍数有：

np\frac np

个。

qq 的倍数有：

nq\frac nq

个。

如果直接计算：

n−np−nqn-\frac np-\frac nq

会出现一个问题。

同时是 pp 和 qq 倍数的数，也就是 pqpq 的倍数，被减掉了两次。

而 pqpq 的倍数有：

npq\frac n{pq}

个。

所以必须加回来一次：

φ(n)=n−np−nq+npq\varphi(n)=n-\frac np-\frac nq+\frac n{pq}

把 nn 提出来：

φ(n)=n(1−1p−1q+1pq)\varphi(n)=n\left(1-\frac1p-\frac1q+\frac1{pq}\right)

括号可以分解：

1−1p−1q+1pq=(1−1p)(1−1q)1-\frac1p-\frac1q+\frac1{pq}=\left(1-\frac1p\right)\left(1-\frac1q\right)

因此：

φ(n)=n(1−1p)(1−1q)\boxed{\varphi(n)=n\left(1-\frac1p\right)\left(1-\frac1q\right)}

6. 三个不同质因子时怎样一步一步数

如果：

n=paqbrcn=p^aq^br^c

其中 p,q,rp,q,r 是三个不同的素数，那么一个数与 nn 互质，就必须同时满足：

  • 不是 pp 的倍数；
  • 不是 qq 的倍数；
  • 不是 rr 的倍数。

从 nn 个整数开始。

先减去 pp 的倍数：

−np-\frac np

再减去 qq 的倍数：

−nq-\frac nq

再减去 rr 的倍数：

−nr-\frac nr

但是这样会把同时含两个质因子的数重复减掉。

例如 pqpq 的倍数既被“去掉 pp 的倍数”减过一次，又被“去掉 qq 的倍数”减过一次，所以要加回来一次：

+npq+\frac n{pq}

同理还要加回来：

+npr+\frac n{pr}

和：

+nqr+\frac n{qr}

现在再看同时是 p,q,rp,q,r 倍数的数。

它们在前面的三个“减法”中一共被减了 3 次，又在三个“加法”中一共被加了 3 次。

这样等于一次都没有删掉。

但这些数显然不与 nn 互质，所以还要再减掉一次：

−npqr-\frac n{pqr}

因此：

φ(n)=n−np−nq−nr+npq+npr+nqr−npqr\varphi(n)=n-\frac np-\frac nq-\frac nr+\frac n{pq}+\frac n{pr}+\frac n{qr}-\frac n{pqr}

把 nn 提出来：

φ(n)=n(1−1p−1q−1r+1pq+1pr+1qr−1pqr)\varphi(n)=n\left(1-\frac1p-\frac1q-\frac1r+\frac1{pq}+\frac1{pr}+\frac1{qr}-\frac1{pqr}\right)

而：

(1−1p)(1−1q)(1−1r)=1−1p−1q−1r+1pq+1pr+1qr−1pqr\left(1-\frac1p\right)\left(1-\frac1q\right)\left(1-\frac1r\right)=1-\frac1p-\frac1q-\frac1r+\frac1{pq}+\frac1{pr}+\frac1{qr}-\frac1{pqr}

所以：

φ(n)=n(1−1p)(1−1q)(1−1r)\boxed{\varphi(n)=n\left(1-\frac1p\right)\left(1-\frac1q\right)\left(1-\frac1r\right)}

这说明乘积公式中的每一项，都在处理“删除倍数时可能重复计算”的问题。

有更多不同质因子时，规律完全相同，只是需要继续处理更多种重复情况。

7. 一般公式

如果：

n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

其中：

p1,p2,…,pkp_1,p_2,\dots,p_k

是 nn 的所有不同质因子，那么：

φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\boxed{\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right)}

每一个不同质因子只出现一次。

8. 用 n=12n=12 检查公式

因为：

12=22×312=2^2\times3

所以不同质因子是：

2, 32,\ 3

公式：

φ(12)=12(1−12)(1−13)\varphi(12)=12\left(1-\frac12\right)\left(1-\frac13\right)

计算：

φ(12)=12×12×23=4\varphi(12)=12\times\frac12\times\frac23=4

实际与 12 互质的数是：

1,5,7,111,5,7,11

正好 4 个。

9. 再看一个例子：φ(18)\varphi(18)

因为：

18=2×3218=2\times3^2

不同质因子只有：

2, 32,\ 3

所以：

φ(18)=18(1−12)(1−13)\varphi(18)=18\left(1-\frac12\right)\left(1-\frac13\right)

得到：

φ(18)=18×12×23=6\varphi(18)=18\times\frac12\times\frac23=6

因此：

φ(18)=6\boxed{\varphi(18)=6}

10. C++ 求单个 φ(n)\varphi(n)

long long phi(long long n) {
    long long ans = n;

    for (long long p = 2; p <= n / p; p++) {
        if (n % p == 0) {
            ans = ans / p * (p - 1);

            while (n % p == 0) {
                n /= p;
            }
        }
    }

    if (n > 1) {
        ans = ans / n * (n - 1);
    }

    return ans;
}

11. 为什么 ans 一开始等于 nn

公式是：

φ(n)=n(1−1p1)(1−1p2)⋯\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots

所以先令：

ans = n;

然后每发现一个新的不同质因子 pp，就把：

1−1p1-\frac1p

乘进去。

12. 为什么写成 ans / p * (p - 1)

因为：

1−1p=p−1p1-\frac1p=\frac{p-1}{p}

所以：

ans(1−1p)=ans⋅p−1pans\left(1-\frac1p\right)=ans\cdot\frac{p-1}{p}

代码写成：

ans = ans / p * (p - 1);

这里在处理质因子 pp 时，当前的 ans 能被 pp 整除，因此先除再乘可以保持整数运算。

13. 为什么要把同一个质因子全部除掉

发现：

p∣np\mid n

以后：

while (n % p == 0) {
    n /= p;
}

会把 pp 的所有次数全部除掉。

例如：

72=23×3272=2^3\times3^2

发现质因子 2 后：

72→36→18→972\rightarrow36\rightarrow18\rightarrow9

这样 2 就不会被重复当成新的质因子处理。

因为欧拉函数公式中，每一个不同质因子只需要出现一次。

14. 为什么只需要试到平方根附近

如果一个大于 1 的整数是合数，那么它至少有一个质因子不超过它的平方根。

否则如果所有非 1 因子都大于平方根，那么任意两个这样的因子相乘都会大于原数，不可能得到原数。

所以不断试除小质因子，就可以把可以分解的部分找出来。

需要注意：代码循环条件中的 n 会随着质因子被除掉而不断变小，因此这里判断的是“当前剩余的 nn”。

代码写成：

p <= n / p

而不是直接写：

p * p <= n

是为了避免当整数很大时，p * p 自身先发生溢出。两种写法在不溢出的情况下表达的是同一个条件。

15. 为什么最后还要判断 n > 1

循环结束以后，可能还剩下一个没有处理过的大质因子。

例如原来：

n=14n=14

先处理质因子 2：

14→714\rightarrow7

剩下的 7 本身是质数。

它还没有进入欧拉函数公式，所以最后要判断：

if (n > 1) {
    ans = ans / n * (n - 1);
}

这里剩下的 n 如果大于 1，就一定是还未处理的一个质因子。

16. 小练习

练习 1

求：

φ(9)\varphi(9)

练习 2

求：

φ(10)\varphi(10)

练习 3

为什么 n=pkn=p^k 时，与 nn 不互质的数恰好是 pp 的倍数？

练习 4

为什么欧拉函数的一般公式中，同一个质因子只出现一次？

17. 答案

练习 1

φ(9)=9−3=6\varphi(9)=9-3=6

练习 2

φ(10)=10(1−12)(1−15)=4\varphi(10)=10\left(1-\frac12\right)\left(1-\frac15\right)=4

练习 3

因为 pkp^k 唯一的质因子是 pp。一个数与 pkp^k 有大于 1 的公共因子，当且仅当它也含有质因子 pp。

练习 4

因为判断是否与 nn 互质，只关心某个质因子是否出现，不关心这个质因子在 nn 中出现多少次。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论