欧拉函数

Tepley · 2025-02-13 16:37:13 · 学习·文化课

1.基础概念

欧拉函数 \varphi(n) 表示在 \le n 的正整数中与 n 互质的数的个数。例如 n = 10 时，在 1.2.3,4,5,6,7,8,9,10 中与 10 互质的数有 1,3,7,9 共 4 个，所以 \varphi(10)=4。

2.计算公式

一个质素 n 可以质因数分解为 p_1^{k1} \times p_2^{k2} \times .... \times p_r^{kr}(其中 k1,k2,k3......kr 可能不是整数)。那么 \varphi(n)=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times......\times(1-\frac{1}{p_r}) = n\prod_{i = 1}^{r}\left(\frac{p-1}{p}\right)。

3.欧拉定理

当 n 和 a 为正整数且互质时，即 \gcd(n,a) = 1，有 a^\varphi(n) \equiv 1 \pmod n。

4.证明欧拉函数为积性函数

在证明之前，先来了解一下映射。

• 单射：设 f:A \to B 为一个映射。如果集合 A 中的任意两个元素 a_1 \ne a_2，都能保证 f(a_1) \ne f(a_2) 那么 f 就是单射。
• 满射：设 f:A \to B 为一个映射。如果对于集合 B 中的任意元素 b，在集合 A 中都能找到一个元素 a，使得 f(a) = b，那么 f 是满射。
• 双射：如果 f:A \to B既是单射又是满射时，那么 f 就是双射。

证明:

1. 集合定义和映射构建
   • 设 m,n 时互质的两个数。
   • 定义集合 A = \left[x \in Z | 1 \le x \le mn, \gcd(x,mn) = 1 \right]。集合 A 中的元素为 \le mn 且与 mn 互质的数，所以集合 A 的大小为 \varphi(mn)。
   • 定义集合 B = \left[(y,z) | y \in Z,1\le y \le m,\gcd(y,m)=1;z \in Z,1\le z\le n,\gcd(z,n) =1 \right]，集合 B 由满足。
   • 构建映射 f:A\to B，对于 x \in A 通过取模运算定义 y = x \bmod m 和 z = x \bmod n，具体来讲，x = qm+y(0 \le y < m,q \in Z) 和 x=pn+z(0 \le z < n,p \in Z)，从而得到 f(x)=(y,z)。
2. 证明 f 是单射
   • 假设 x_1,x_2 \in A，且 f(x_1) = f(x_2)，即 (x_1 \bmod m，x_1 \bmod n) = (x_2 \bmod m,x_2 \bmod n)。根据同余的定义，x_1 \bmod m = x_2 \bmod m \Rightarrow x_1 \equiv x_2 (\bmod m)。这就等价于存在一个整数 k 使得 x_1 - x_2 = km，也就是 m \mid (x_1-x_2)；同理，x_1 \bmod n = x_2 \bmod n \Rightarrow x_1 \equiv x_2 (\bmod n)。即存在一个整数 l，使得 x_1 - x_2 = ln，也就是 n \mid (x_1 - x_2)。因为 \gcd(m,n) = 1，根据数论中的结论，若 m 能整除 a，n 也能整除 a，那么 mn 也能整除 a。在这里 a = x_1 - x_2，所以 mn \mid (x_1 - x_2)，即存在整数 s，使得 x_1-x_2=smn。又因为 x_1,x_2 \in \left[1,2,3,......,mn\right]，在此范围内，如果上式成立，只有当 s= 0 时，即 x_1 = x_2，所以 f 是单射。