欧拉函数 φ(n)：找一找你身边有多少“互质朋友”

你有没有想过，一个数字也有自己的“朋友圈”？在这个朋友圈里，每个朋友都和它“没有共同的秘密”（除了1这个全民朋友）。而这个朋友圈的大小，就是欧拉函数要告诉我们的。欧拉函数是数论中的一把钥匙，它帮我们理解数字之间的模运算关系，是密码学（比如RSA加密）的重要工具。今天我们就来认识它，先用最直白的方式理解它怎么算、有什么用。

什么是互质？—— 两个人有没有“秘密朋友”？

在认识欧拉函数之前，我们得先搞明白一个概念——“互质”。两个数互质，就是指它们除了1以外没有其他的公共因数。比如：

• 8和9：8的因数是1、2、4、8；9的因数是1、3、9。公共因数只有1，所以8和9互质。
• 12和18：12的因数是1、2、3、4、6、12；18的因数是1、2、3、6、9、18。公共因数有1、2、3、6，除了1还有别的，所以它们不互质。

你还可以把互质想象成“两个人之间没有共同的秘密朋友”。如果两个人只有一个共同的朋友（1号），他们就互质；如果有其他共同朋友（比如2号、3号），他们就不互质。就像你和你的同桌，如果你们只有一个共同的朋友（1号），那说明你们俩的关系“很干净”；如果你们还有第二个共同的朋友（比如你们都是篮球社团的成员），那你们的“秘密朋友”就不止一个啦。

生活中的例子

• 分数化简：要化简分数 8/9，因为8和9互质，分子分母不能再约分；而 12/18 不互质，可以约分为 2/3。
• 排队分组：班级有24人，想分成每4人一组做游戏，那么4和24就不互质（因为4是24的因数），意味着有人会落单或重复分组？但更贴切的是：如果两个数的最大公约数大于1，说明它们有“共同因子”，就像两个人都在同一个课外班里，分工时可能重复或冲突。

欧拉函数到底是什么？—— 一个数字的“互质朋友”数量

欧拉函数用希腊字母 φ 表示，读作“fai”。 φ(n) 表示：在1到n这个范围内（包括1和n），有多少个整数与n互质。

举个例子：

• n = 6。从1到6的所有数是：1, 2, 3, 4, 5, 6。我们看看每个数与6是否互质：

  • 1和6：只有公共因数1，互质。
  • 2和6：公共因数有1和2（因为2能整除6），不互质。
  • 3和6：公共因数有1和3，不互质。
  • 4和6：4的因数1,2,4；6的因数1,2,3,6；公共1和2，不互质。
  • 5和6：只有1，互质。
  • 6和6：公共1,2,3,6，不互质。 所以互质的数有1和5，一共2个。因此 φ(6) = 2。

• n = 5。5是质数。从1到5：1,2,3,4,5。质数只有因数1和它自己。所以除了5本身，其他数都与5没有公因数（除了1）。所以1,2,3,4都与5互质。共4个。但注意：5本身与5不互质（因为公因数有5）。所以 φ(5) = 4。

你发现规律了吗？对于质数p，1到p-1的所有数都和p互质，所以 φ(p) = p - 1。

• n = 1。按照定义，1到1只有1本身，而1与1是互质的吗？通常认为1与任何数都互质（因为1只有一个因数1），所以 φ(1) = 1。

新手容易犯的错误

1. 认为 φ(1) = 0：因为1和1有公因数1，但他们忘了“互质”的定义是“只有1是公因数”，而1自己确实只有1这一个因数，所以1和自己互质。就像一个只有自己的朋友，也算朋友。所以 φ(1)=1，不是0。
2. 计算 φ(p) 时忘记去掉自身：比如质数7，有人会误以为1~7全部都与7互质，得出7。但7和7的公因数是7，不互质，所以应该是6。
3. 认为 φ(n) 一定等于 n-1：只有当n是质数时才成立。对于合数，比如6，φ(6)=2，远小于5。别被“质数特例”迷惑了。
4. 检查互质时只考虑质因数：比如判断8和12是否互质，有人只看质因数：8=2³，12=2²×3，有公因数2，所以不互质，这没错。但有人可能会误以为只要两个数没有相同的质因数就是互质，这其实是正确的（因为公因数都是由质因数组合而成）。注意：1没有质因数，所以任何数与1都互质。

欧拉函数的意义：它到底有什么用？

欧拉函数最核心的应用是在密码学中，尤其是RSA加密算法。RSA加密利用了“大数分解困难”的特性，而欧拉函数帮助计算加密和解密的关键参数。此外，欧拉定理（我们后面会讲到）也依赖于欧拉函数，它用来处理模幂运算，比如在快速计算 a^b mod n 时常常用到。

把欧拉函数想象成“一个数字的互质朋友数量”。比如6有2个互质朋友（1和5）。当我们在做模6的运算时，只有这2个朋友有特殊的“逆元”性质（即它们能找到另一个数，使得乘积模6等于1）。这一点在后面的欧拉定理中会非常重要。

生活中的类比

假设你有一个密码锁，密码是数字n。只有那些与n互质的数字才能作为“钥匙”的一部分，因为它们有特殊的数学性质，可以让你通过某种运算解开锁。而欧拉函数就告诉你这样的“有效钥匙”有多少个。比如n=10，互质的数字有1,3,7,9共4个，那么你的密码系统就只有4种基本“钥匙”可用——当然实际加密中n非常大，有上亿种可能。

如何计算欧拉函数？—— 暴力方法

最直接的方法是：从1到n遍历每个数，判断它和n是否互质。判断互质可以用最大公约数（gcd）：如果 gcd(i, n) == 1，则互质。

对于小数字，这没问题。但如果n很大（比如10^9），遍历所有数就太慢了。所以我们需要更聪明的计算方法，这就引出了下一篇文章中的欧拉函数性质与公式。

不过作为初学者，我们先掌握暴力写法，理解其含义。

C++ 代码示例（暴力求欧拉函数）

#include <iostream>
using namespace std;

// 计算最大公约数（辗转相除法）
int gcd(int a, int b) {
    while (b) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 暴力计算 n 的欧拉函数值
int phi(int n) {
    int count = 0;           // 记录互质的个数
    for (int i = 1; i <= n; i++) {
        if (gcd(i, n) == 1) {   // 如果 i 和 n 的最大公约数是 1，说明互质
            count++;
        }
    }
    return count;
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;
    cout << "φ(" << n << ") = " << phi(n) << endl;
    return 0;
}

代码中我们用辗转相除法求两个数的最大公约数。循环从1到n，检查每个数是否与n互质，统计个数。注意：i从1开始，n本身也要判断，因为 i=n 时 gcd(n,n)=n，不互质，所以不会计数。

Python 代码示例（暴力求欧拉函数）

# 计算最大公约数（辗转相除法）
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 暴力计算 n 的欧拉函数值
def phi(n):
    count = 0
    for i in range(1, n + 1):
        if gcd(i, n) == 1:   # 如果 i 和 n 的最大公约数是 1，则互质
            count += 1
    return count

# 主程序
n = int(input("请输入一个正整数 n: "))
print(f"φ({n}) = {phi(n)}")

Python 的写法更加简洁，但思想与 C++ 完全一样。

完整运行示例

假设我们运行程序并输入10，程序输出：φ(10) = 4。这与我们前面表格一致。你可以自己试试输入12、15等数字，看看结果是否和手动计算的一致。

进一步理解：欧拉函数的值有什么特点？

观察几个 n 的值：

可以看到，质数的欧拉函数值就是它自己减1（如 φ(7)=6）。对于质数的幂比如 9=3^2，φ(9)=6，它等于 3^2 - 3^1 = 9 - 3 = 6。这个规律我们下一篇文章会系统讲解。

你可能会问：为什么欧拉函数的值都是偶数（除了1）？其实不是，比如 φ(2)=1 是奇数，但一般 n>2 时 φ(n) 是偶数。因为如果 a 与 n 互质，那么 n-a 也与 n 互质，它们成对出现（除了 a=n/2 的情况，但 n>2 时 n/2 不会与 n 互质）。所以互质的数总是成对出现，从而 φ(n) 是偶数。这个性质也很有趣。

另外，注意 φ(1)=1 是个特例。当n=2时，φ(2)=1，也是奇数，因为只有1这一个互质数，没有配对的对象。

总结与延伸

欧拉函数 φ(n) 统计了1到n中与n互质的数的个数。它是数论中非常基础的概念，是后续学习欧拉定理和RSA密码的基础。你可以从暴力算法开始理解它，但实际应用中我们会用更高效的公式计算，这将是我们下一篇文章的内容。

记住：互质就是“没有共同的因数（除了1）”。欧拉函数就是“找朋友”，看看一个数有多少个“互质朋友”。当你遇到需要计算模逆元或幂模运算时，欧拉函数就会派上大用场。

接下来，我们继续学习欧拉函数的性质和通用计算公式，让你能快速算出任意 n 的 φ 值。同时，你还会学到欧拉定理（a^φ(n) ≡ 1 mod n），它可是密码学中的大明星！