数论 · 欧拉定理
pldzy
·
·
个人记录
UPDATE
扩欧拉证明，待填坑。
1 欧拉函数
举例：$\varphi(8)=4$，分别是：1、3、5、7。
注意：$\varphi(1)=1$。
------------
### 引理 1
#### 引理 1.1：当 $n$ 为质数时，有 $\varphi (n)=n-1$。
证明：满足条件的数为 1 到 $n-1$。
#### 引理 1.2：若 $n=p^k$ 且 $p$ 为质数时，$\varphi(n)=(p-1)*p^{k-1}$。
证明：
比 $n$ 小的整数中，只有 $p*t\ (t \in [1,p^{k-1}-1])$ 这些数与 $n$ 不互质。
所以 $\varphi (n)=p^k-1-(p^{k-1}-1)=p^k-p^{k-1}=(p-1) * p^{k-1}$。
证毕。
#### 引理 1.3：若 $n=a* b$ 且 $a\perp b$，则 $\varphi (n)=\varphi(a) * \varphi (b)$。
**说白了，就是函数 $\varphi$ 为积性函数。**
证明：
易知，与 $a$ 互质的数有 $\varphi(a)$ 个，与 $b$ 互质的数有 $\varphi (b)$ 个。
那么一个数 $x$ 要想与 $n$ 互质，则必须满足同时与 $a$ 和 $b$ 都互质。
所以 $\varphi(n)=\varphi (a)* \varphi (b)$。
证毕。
------------
### 引理 2
设 $n = p_1^{a_1} * p_2^{a_2} * \cdots * p_k^{a_k}$。
根据引理 1.3，有：
$$\varphi (n)= \varphi(p_1^{a_1}) * \varphi (p_2^{a_2})* \cdots \varphi (p_k^{a_k})$$
根据引理 1.2，有：
$$\text{右式} = p_1^{a_1} * p_2^{a_2} * \cdots * p_k^{a_k} * (1 - \dfrac {1}{p_1}) * (1-\dfrac{1}{p_2})*\cdots * (1-\dfrac {1}{p_k})$$
综上，我们可以得到：
$$\varphi (n) = n * (1 - \dfrac {1}{p_1}) * (1-\dfrac{1}{p_2})*\cdots * (1-\dfrac {1}{p_k})$$
## 2 欧拉定理
### 结论
$\text{当 }a\perp m\ \text{时, 有 } a^{\varphi(m)} \equiv 1 \pmod m$。
### 证明：
建变量 $p$，使 $p \gets a * x_i$。此处 $x_i$ 为第 $i$ 大的与 $m$ 互质的数。
#### 1 $p$ 之间两两不同
即 $\forall\ i, j\ \ (i\ne j)\ p_i - p_j \ne 0 \bmod m
证明：因为 x_i 必定两两不同，证毕。
2 p_i \% m 只有 \varphi 种不同的取值
设 p_i=km+r，即 ax_i-km = r。
易知 \gcd (a, m)=1，此时最后解出来的 x_i 必定还要乘上 r。
因为 x_i \perp m，所以 \gcd (r,m)=1。
3
综合 1、2 可以得出 p_i \% m 和 x_i 是一一对应的。
所以 \prod_{i=1}^{\varphi(m)} p_i \equiv \prod_{i=1}^{\varphi(m)} x_i \pmod m,
即 a ^ {\varphi(m)}\prod_{i=1}^{\varphi(m)} x_i \equiv \prod_{i=1}^{\varphi(m)} x_i \pmod m，
化简，得到：a^{\varphi(m)} \equiv 1 \pmod m。
证毕。
板子题：P5091 【模板】扩展欧拉定理
3 扩展欧拉定理
无需 a \perp m，求解 a^c \bmod m
-
当 c < \varphi(m) 时，答案为 a^c；
-
当 c = \varphi (m) 时，答案为 1；
-
当 c > \varphi (m) 时，答案为 a ^ {(c \bmod \varphi (m)) + \varphi(m)}。
证明啊，问就是看得懂，但自己证不出。
——End——