数论基础之欧拉函数

欧拉函数
¶

今天学习一些欧拉函数及其相关的性质和定理：

欧拉函数 $φ (N)$ ：
$φ (N)$ 表示 ${1, 2, 3, \dots, N - 1}$ 中与 $N$ 互质的数的个数。
数论欧拉定理：
当 $a$ 和 $N$ 互质时，有： $a^{φ (N)} \equiv 1 \mod N$
广义欧拉定理：
当 $a$ 和 $N$ 不互质时，有：
$a^{b} \equiv {\begin{aligned} a^{b} \mod N, & 0 ⩽ b < φ (N) \\ a^{(b \mod φ (N)) + φ (N)} \mod N, & b ⩾ φ (N) \end{aligned}$
欧拉函数的一些性质
- 【性质1】若 $N = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{s}^{k_{s}}$ ，则：
  $φ (N) = N \cdot (1 - \frac{1}{p_{1}}) \cdot (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{s}})$
  证明见模方程基础之筛法
- 【性质2】若 $X$ 和 $Y$ 是互质的两个正整数，则：
  $φ (X \cdot Y) = φ (X) \cdot φ (Y)$

同余类与剩余系
¶

如果 $a \equiv b \mod N$ ，则成 $a, b$ 模 $N$ 同余。

同余类： ${a - k N, a - k N + N, \dots, a, a + N, \dots, a + k N}$ 构成一个模 $N$ 的同余类
完全剩余系：如果 ${a_{1}, a_{2}, \dots, a_{N}}$ 两两模 $N$ 不同余，则称其为模 $N$ 的一组完全剩余系
既约剩余系：如果 ${a_{1}, a_{2}, \dots, a_{φ (N)}}$ 两两模 $N$ 不同余且均和 $N$ 互质，则称其为模 $N$ 的一组既约剩余系

数论欧拉定理
¶

如果 $gcd (λ, N) = 1$ ，那么 $λ^{φ (N)} \equiv 1 \mod N$ 。这个定理被称为数论欧拉定理 ^[1]。

在证明数论欧拉定理之前，先看下面两个定理。

定理1
¶

如果 $gcd (λ, N) = 1$ 且 ${a_{1}, a_{2}, \dots, a_{φ (N)}}$ 是一组模 $N$ 的既约剩余系，则 ${λ \cdot a_{1}, λ \cdot a_{2}, \dots, λ \cdot a_{φ (N)}}$ 也是一组模 $N$ 的既约剩余系。

因为 $gcd (λ, N) = 1$ ，且由 ${a_{1}, a_{2}, \dots, a_{φ (N)}}$ 构成模 $N$ 的既约剩余系，有 $gcd (a_{i}, N) = 1$ ，进而有 $gcd (λ \cdot a_{i}, N) = 1$ 。
若 $λ \cdot a_{i} \equiv λ \cdot a_{j} \mod N$ ，则 $λ \cdot (a_{i} - a_{j}) \equiv 0 \mod N$ ，即 $λ \equiv 0 \mod N$ 或 $(a_{i} - a_{j}) \equiv 0 \mod N$ 。但这显然是不可能的，故有 $λ \cdot a_{1}, λ \cdot a_{2}, \dots, λ \cdot a_{φ (N)}$ 两两模 $N$ 不同余。
这就证明了 ${λ \cdot a_{1}, λ \cdot a_{2}, \dots, λ \cdot a_{φ (N)}}$ 也是一组模 $N$ 的既约剩余系。

定理2
¶

如果 $c \cdot a \equiv c \cdot b \mod N$ ，那么有 $a \equiv b \mod \frac{N}{gcd (c, N)}$ .

因为 $c \cdot a \equiv c \cdot b \mod N$ ，所以有 $N ∣ c \cdot (a - b)$ ，即 $\frac{N}{gcd (c, N)} | \frac{c}{gcd (c, N)} \cdot (a - b)$ 。
又因为 $\frac{N}{gcd (c, N)}$ 和 $\frac{c}{gcd (c, N)}$ 互质，所以必有 $\frac{N}{gcd (c, N)} | (a - b)$ 。因此， $a \equiv b \mod \frac{N}{gcd (c, N)}$

数论欧拉定理证明
¶

如果 $gcd (λ, N) = 1$ ，那么 $λ^{φ (N)} \equiv 1 \mod N$ .

如果 ${a_{1}, a_{2}, \dots, a_{φ (N)}}$ 是一组模 $N$ 的既约剩余系，由【定理1】可知， ${λ \cdot a_{1}, λ \cdot a_{2}, \dots, λ \cdot a_{φ (N)}}$ 也是一组模 $N$ 的既约剩余系。
所以， $\prod_{i = 1}^{φ (N)} (a_{i} \mod N) \equiv \prod_{i = 1}^{φ (N)} (λ \cdot a_{i} \mod N)$
即， $\prod_{i = 1}^{φ (N)} (a_{i} \mod N) \equiv λ^{φ (N)} \prod_{i = 1}^{φ (N)} (a_{i} \mod N)$
又因为， $gcd (\prod_{i = 1}^{φ (N)} (a_{i} \mod N), N) = 1$ 且 $gcd (λ^{φ (N)}, N) = 1$
所以由【定理2】有： $λ^{φ (N)} \equiv 1 \mod N$

费马小定理
¶

特别地，如果 $p$ 是一个素数，那么有 $φ (p) = p - 1$ ，且：

如果 $gcd (λ, p) = 1$ ，由【数论欧拉定理】，有
$λ^{p} = λ^{φ (p) + 1} \equiv 1 \cdot λ \mod p \equiv λ \mod p$
如果 $gcd (λ, p) \neq 1$ ，因为 $p$ 是一个素数，则必有 $gcd (λ, p) = p$ ，所以
$λ^{p} \equiv 0 \mod p \equiv λ \mod p$

综上，对于任意整数 $λ$ 都有 $λ^{p} \equiv λ \mod p$ 。这就是著名的费马小定理。

广义欧拉定理
¶

如果 $gcd (λ, N) \neq 1$ 呢？

首先，由于 $λ^{i} \mod N \in [0, N - 1]$ ，由鸽巢原理可知，必存在 $i (0 ⩽ i ⩽ N - 1)$ 使得 $λ^{N} \equiv λ^{i} \mod N$ 。可能你会想，那岂不是 $λ^{N - i} \equiv 1 \mod N$ ？但事实并不是这样的，这样想的读者忽略了 $gcd (λ, N) \neq 1$ ：

由 $N | λ^{i} \cdot (λ^{N - i} - 1)$ ，不难有： $\frac{N}{gcd (N, λ^{i})} | (λ^{N - i} - 1)$ ，
所以只能得出 $λ^{N - i} \equiv 1 \mod \frac{N}{gcd (N, λ^{i})}$ 。

事实上，由扩展欧几里得定理可知，方程 $λ \cdot x + N \cdot y = 1 \neq gcd (λ, N)$ 无解，那么就不存在 $λ$ 在模 $N$ 意义下的逆元。进而推知，不存在整数 $b$ 使得 $λ^{b + 1} \equiv 1 \mod N$ ，因为如果存在，那 $λ^{b}$ 就是 $λ$ 模 $N$ 意义下的逆元了，矛盾。

尽管如此，由鸽巢原理的分析，我们知道存在一个最小的 $L$ 和一个足够大的整数 $δ$ ，使得当 $x ⩾ δ$ 时，有 $λ^{L + x} \equiv λ^{x} \mod N$ .

接下来，我们将证明当 $N = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{s}^{k_{s}}$ 时， $δ = max {k_{i}}, (1 ⩽ i ⩽ s)$ 且 $L ∣ φ (N)$ .

不妨假设 $N = p^{k} \cdot X$ ，其中， $k ⩾ 1$ 且 $gcd (p^{k}, X) = 1$ 。

定理3
¶

$φ (X) ∣ φ (N)$

因为 $gcd (p^{k}, X) = 1$ ，由【性质2】可知： $φ (N) = φ (X) \cdot φ (p^{k})$ .
所以， $φ (X) ∣ φ (N)$

定理4
¶

$p^{φ (N) + k} \equiv p^{k} \mod N$

由于 $gcd (p, X) = 1$ ，根据欧拉定理，有 $p^{φ (X)} \equiv 1 \mod X$ .
所以，存在一个整数 $t$ 使得 $p^{φ (X)} = t X + 1$ . 于是有 $p^{k} \cdot p^{φ (X)} = t X \cdot p^{k} + p^{k}$ ，即 $p^{φ (X) + k} = t N + p^{k} \equiv p^{k} \mod N$ .
不难得出：对于任意整数 $s$ 都满足 $p^{s \cdot φ (X) + k} \equiv p^{k} \mod N$ .
由【定理3】可知， $\frac{φ (N)}{φ (X)}$ 是一个整数，即当 $s = \frac{φ (N)}{φ (X)}$ 时，有 $p^{φ (N) + k} \equiv p^{\frac{φ (N)}{φ (X)} \cdot φ (X) + k} \equiv p^{k} \mod N$

推论4-1
¶

对于任意非零整数 $s$ ，都有 $(p^{s})^{φ (N) + k} \equiv (p^{s})^{k} \mod N$ .

由【定理4】可知， $(p^{s})^{φ (N) + k} = p^{s \cdot φ (N) + s \cdot k} \equiv p^{s \cdot k} \mod N \equiv (p^{s})^{k} \mod N$

定理5
¶

若 $c = a \cdot b$ 满足 $a^{L + x} \equiv a^{x} \mod N$ 且 $b^{L + x} \equiv b^{x} \mod N$ ；那么， $c^{L + x} \equiv c^{x} \mod N$ .

$c^{L + x} = a^{L + x} \cdot b^{L + x} \equiv a^{x} \cdot b^{x} \mod N \equiv c^{x} \mod N$

定理6
¶

记 $N = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{s}^{k_{s}}$ ，若 $gcd (λ, N) \neq 1$ ，则对于任意满足 $r ⩾ max {k_{i}}, (1 ⩽ i ⩽ s)$ 的整数 $r$ ，有 $λ^{r + φ (N)} \equiv λ^{r} \mod N$ .

将 $λ$ 唯一分解为 $λ = q_{1}^{a_{1}} \cdot q_{2}^{a_{2}} \dots q_{t}^{a_{t}}$ .
若 $gcd (q_{j}, N) = 1$ ，由【数论欧拉定理】可知 $q_{j}^{φ (N)} \equiv 1 \mod N$ 所以，对于任意整数 $r$ 有
$q_{j}^{φ (N) + r} \equiv q_{j}^{r} \mod N$
若 $gcd (q_{j}, N) \neq 1$ ，不妨设 $q_{j} = p_{i}$ ，由【定理4】可知，当 $r ⩾ k_{i}$ 时，有
$q_{j}^{φ (N) + r} \equiv q_{j}^{r} \mod N$
综上，不难发现，当 $r ⩾ max {k_{i}}$ 时，对任意 $1 ⩽ j ⩽ t$ ，有：
$q_{j}^{φ (N) + r} \equiv q^{r} \mod N$
结合【推论4-1】，对于任意 $1 ⩽ j ⩽ t$ ，有：
$(q_{j}^{a_{j}})^{φ (N) + r} \equiv (q_{j}^{a_{j}})^{r} \mod N$
结合【定理5】有：当 $r ⩾ max {a_{i}}$ 时，有

广义欧拉定理
¶

若 $N = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{s}^{k_{s}}$ ，则无论 $a$ 和 $N$ 互质与否，当 $b ⩾ ϕ (N)$ 时，都有：

a^{b} \equiv a^{(b \mod φ (N)) + φ (N)} \mod N

当 $a$ 和 $N$ 互质时，根据【数论欧拉定理】，结论显然成立。
当 $a$ 和 $N$ 不互质时，由于 $φ (N) ⩾ p_{i}^{k_{i} - 1} ⩾ k_{i}, (1 ⩽ i ⩽ s)$ ，
即 $φ (N) ⩾ max {k_{i}}$ ，结合【定理6】可知结论成立。

练习
¶

#	problems	categories	solution
1	FZU/Super A^B mod C	广义欧拉定理	solution.cpp

小结
¶

鉴于本人能力有限，有误之处还望指证。

欧拉函数¶

同余类与剩余系¶

数论欧拉定理¶

定理1¶

定理2¶

数论欧拉定理证明¶

费马小定理¶

广义欧拉定理¶

定理3¶

定理4¶

推论4-1¶

定理5¶

定理6¶

广义欧拉定理¶

练习¶

小结¶

欧拉函数
¶

同余类与剩余系
¶

数论欧拉定理
¶

定理1
¶

定理2
¶

数论欧拉定理证明
¶

费马小定理
¶

广义欧拉定理
¶

定理3
¶

定理4
¶

推论4-1
¶

定理5
¶

定理6
¶

广义欧拉定理
¶

练习
¶

小结
¶