欧拉函数与欧拉定理：数字朋友的“交友圈”和“回环魔法”

从“找朋友”开始理解欧拉函数

想象一下，你有一群数字朋友，比如1、2、3、4、5、6。但只有那些和你指定的数字n“关系铁”的朋友，才能加入你的“铁杆好友圈”。怎么判断关系铁不铁？就看它们和n的最大公因数是不是1。如果最大公因数是1，说明它们和n没有公共因子（除了1），像真正的朋友一样“互相不藏着私心”；如果最大公因数大于1，说明它们和n有共同的“秘密”（公因子），那就不能算铁杆。

欧拉函数φ(n)就是专门来数一数，在1到n之间（包括1和n），有多少个数字和n是“铁杆关系”（互质）。比如n=6：1和6的最大公因数是1，2和6的最大公因数是2（不铁），3和6最大公因数是3，4和6最大公因数是2，5和6最大公因数是1，6和6最大公因数是6。所以只有1和5两个铁杆朋友，因此φ(6)=2。

生活中，这就像在一个班级里，只有那些和你没有“共同小团体”（共同因子）的同学，你才愿意和他们一起组队参加数学竞赛。欧拉函数就是帮你数出这个“专属竞赛队友”的数量。

欧拉函数的计算公式：像剥洋葱一样分解质因数

公式长什么样？

如果n可以分解成质因数的乘积，比如：

n = p1^a1 × p2^a2 × ... × pk^ak

其中p1、p2都是质数（比如2、3、5、7……），那么欧拉函数可以用一个简洁的公式计算：

φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)

这什么意思呢？举个例子，n=12，质因数分解是 12=2²×3。那么：

φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4

确实，1到12中和12互质的数有：1、5、7、11，一共4个。

为什么这个公式有效？

你可以想象：先从小到大的数字里“筛掉”所有是2的倍数的数字（因为和2有公因子），再“筛掉”所有是3的倍数的数字。但是注意，即同时是2和3的倍数的数字（比如6、12）已经被筛过两次？其实公式中的乘法正好避免了重复：第一次去掉 1/2 的数字，剩下 n × (1 - 1/2)；第二次去掉剩下部分中 1/3 的数字，也就是 n × (1 - 1/2) × (1 - 1/3)。就像剥洋葱，一层一层去掉“坏朋友”，最后剩下的就是铁杆。

质数的情况

如果n本身就是一个质数，比如7，那么它的质因数只有它自己：7=7¹。代入公式：

φ(7) = 7 × (1 - 1/7) = 6

果然，1到7中和7互质的数有1、2、3、4、5、6，一共6个。所以质数的欧拉函数值就是它减1。

生活中，质数就像班里唯一的“独行侠”，其他所有同学（1到n-1）都和它没有共同爱好（公因子），所以朋友最多。

欧拉定理：走圈圈的数学魔法

欧拉定理说的是：如果a和n互质（它们是铁杆朋友），那么a的φ(n)次方除以n的余数一定等于1。用数学公式写：

a^φ(n) ≡ 1 (mod n)

其中“≡”表示“同余”，就是两数除以n的余数相等。

用钟表比喻来理解

想象一个钟表只有n个刻度（从0到n-1）。你每步走a格，从0开始走。因为a和n互质，你的步长就不会在某个刻度上卡住（比如n=6，a=2时，步长2就会在0、2、4之间循环，永远到不了1、3、5）。现在，你连续走φ(n)步，神奇的事情发生了：你一定会回到起点0。这就像被施了魔法，步数刚刚好。

实际上，如果你从1开始走，走φ(n)步后，你会到达1的位置，也就是余数为1。

生活中的例子

假设班里有n=8位同学（编号0-7），你每次发糖给编号为a=3的同学，然后让他把糖传给步长为3的下一位。你发一次糖，就相当于走一步。因为3和8互质，你会发现，发够φ(8)=4次糖后，糖又回到了你最开始给的那位同学手中，也就是“走了4圈”回到了起点。

欧拉定理在密码学中非常有用，比如RSA加密算法就靠它来保证安全性。

代码实现：亲手算算你数字的铁杆朋友

下面是一个C++程序，能帮你计算任意正整数n的欧拉函数值。代码里用了“质因数分解”的思想，边找质因子边更新结果。

代码解释

#include <iostream>
using namespace std;

// 计算欧拉函数 φ(n)
int eulerPhi(int n) {
    int result = n; // 先设结果为n，后面逐步“筛掉”因子
    int temp = n;   // 临时变量，用于逐步分解
    // 从最小的质数2开始尝试，直到sqrt(temp)
    for (int p = 2; p * p <= temp; p++) {
        if (temp % p == 0) {          // 找到p是temp的一个质因子
            while (temp % p == 0) {   // 把temp中所有p因子全部除掉
                temp /= p;
            }
            result -= result / p;     // 等价于 result = result * (1 - 1/p)
        }
    }
    // 如果最后temp还大于1，说明它本身就是一个质因子
    if (temp > 1) {
        result -= result / temp;
    }
    return result;
}

int main() {
    cout << "φ(12) = " << eulerPhi(12) << endl;   // 输出4
    cout << "φ(7) = " << eulerPhi(7) << endl;     // 输出6（质数时等于n-1）
    cout << "φ(1) = " << eulerPhi(1) << endl;     // 特殊：φ(1)=1
    cout << "φ(100) = " << eulerPhi(100) << endl; // 分解为2²×5²，结果40
    return 0;
}

代码运行后你会看到

φ(12) = 4
φ(7) = 6
φ(1) = 1
φ(100) = 40

• φ(1)=1 是因为1和任何数（包括自己）互质，所以只有它自己一个朋友。
• φ(100)=40 可以手动验证：1到100中和100互质的数有40个（尾数不是0或5，且不是2的倍数，但注意同时满足条件）。

代码里的关键点

1. 为什么循环到 p*p <= temp？因为如果temp有一个大于sqrt(temp)的质因子，那么它肯定只有一个（另一个因子会小于sqrt(temp)已经被处理过），最后单独处理即可。
2. result -= result / p 就是计算 result * (1 - 1/p) 的整数形式。例如result=12, p=2：result -= 12/2 = 6，得到6，相当于 12 * 1/2 = 6。
3. 最后处理temp>1的情况：如果temp经过循环后还大于1，说明它本身是一个未被除尽的质数（比如n=7，循环到p=2发现2²=4>7，所以没进入循环，temp=7>1），那么直接乘上(1-1/temp)。

常见错误与避坑指南

错误1：忘记处理最终的质因子

很多新手在循环结束后，忘记判断temp>1的情况。比如输入n=7时，循环p* p<=temp的条件一开始就不成立（p=2, 4<=7成立，但7%2!=0，循环继续p=3,9<=7不成立，结束），此时temp=7>1，就要处理。如果漏了，结果会错误变成7（因为没去掉质因子7本身），而不是正确的6。

正确做法：始终在循环末尾检查temp。

错误2：循环条件写错

比如有人会写成 p <= temp，这样会循环很多次，而且对于质数，temp会一直不变，导致p不断增大直到等于temp，效率很低。正确写法是 p * p <= temp，因为如果一个合数有大于sqrt的因子，那么它一定有一个小于sqrt的因子，我们只需检查小因子就行。

错误3：混淆了“互质”和“质数”

互质是指两个数的最大公因数为1，并不要求每数本身是质数。比如n=8时，3和8互质，但3是质数，9和8互质但9不是质数。

错误4：误以为欧拉函数可以递归计算

虽然有递归公式，但用循环分解是最高效的，初学者不要乱用递归。

完整的可运行代码示例

下面是一个完整的程序，你可以直接复制到你的IDE里运行：

#include <iostream>
using namespace std;

// 计算欧拉函数 φ(n)
int eulerPhi(int n) {
    int result = n; // 初始值设为n
    int temp = n;   // 临时变量，用于分解
    for (int p = 2; p * p <= temp; p++) {
        if (temp % p == 0) {          // 找到质因子p
            while (temp % p == 0) {   // 除去所有p
                temp /= p;
            }
            result -= result / p;     // 应用公式
        }
    }
    if (temp > 1) {                   // 处理最后一个质因子
        result -= result / temp;
    }
    return result;
}

int main() {
    int num; // 输入的数字
    cout << "请输入一个正整数：";
    cin >> num;
    cout << "φ(" << num << ") = " << eulerPhi(num) << endl;
    return 0;
}

你可以输入任意整数，比如输入12，会输出4；输入100，输出40。

相关指引：从欧拉函数到更多数学魔法

学会欧拉函数后，你可以继续探索下面这些有趣的知识：

• 欧拉定理的推广：费马小定理
  当n是质数p时，欧拉定理变成a^(p-1) ≡ 1 (mod p)，这就是费马小定理，在快速幂取模和素数测试中很有用。

• 乘法逆元
  在模运算中，如果你要计算a/b mod m，可以利用欧拉定理得到b的逆元（当b与m互质时），让除法变成乘法。

• RSA加密算法
  这正是欧拉定理最著名的应用之一。它利用大数分解的困难性和欧拉定理的结论，实现了公开密钥加密。

• 扩展欧几里得算法
  用来求最大公因数和解同余方程，和欧拉函数是数论中的好搭档。

你可以试着用上面的代码算一算φ(2024)、φ(9999)，看看你的数字有多少铁杆朋友！