欧拉函数

1.基础概念

2.计算公式

3.欧拉定理

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$ 是单射。