参考资料
同余
定义
- 设$m \neq 0$, 若$m | (a - b)$ ,称$m$为模数，$a$同余于$b$模$m$，$b$是对$a$模$m$的剩余，记作$a \equiv b\kern2pt(mod \kern2pt m)$。
欧拉函数
定义
- 小于等于$n$和$n$互质的数的个数，记作$\varphi(n)$。
性质
- 欧拉函数为积性函数。即对任意满足$gcd(a, b) = 1$，有$\varphi(ab) = \varphi(a)\varphi(b)$。
- 设$n = \prod_{i = 1}^{s}\rho_{i}^{k_{i}}$，其中$\rho_{i}$是质数，$\varphi(n) = n \times \prod_{i= 1}^{s}\frac{\rho_{i} - 1}{\rho_{i}}$。
证明
PlanA
- 容斥定理。基本思路为去掉$[1-n]$中所有$\rho_{i}$的倍数。
$$ \varphi(n) = n - \frac{n}{\rho_{1}} - \frac{n}{\rho_{2}} \dots -\frac{n}{\rho_{s}} \\ + \frac{n}{\rho_{1} \rho_{2}} + \frac{n}{\rho_{1}\rho_{3}} + \dots +\frac{n}{\rho_{s - 1}\rho_{s}} \\ - \frac{n}{{\rho_{1}\rho{2}\rho{3}}} \dots $$
PlanB
- 由积性函数性质可得$\varphi(n) = \prod_{i = 1}^{s}\varphi(\rho_{i}^{k_{i}})$。
从欧拉函数定义可得$\varphi(\rho_{i}^{k_{i}})$为所有小于等于$\rho_{i}^{k_{i}}$且与$\rho_{i}^{k_{i}}$互质的数，又由于$\rho_{i}$为质数，所以互质的数为$\rho_{i}, 2\rho_{i}, 3\rho{i} \dots, (\rho_{i}^{k_{i}} - 1) \rho_{i}$，即每$\rho_{i}$个数中有一个与$\rho_{i}$互质的数。因此可得，$\varphi(\rho_{i}^{k_{i}}) = \rho_{i}^{k_{i}} - \rho_{i}^{k_{i} - 1}$。
$$ \begin{align*} \varphi(n) &= \prod_{i = 1}^{s}\rho_{i}^{k_{i}}(1 - \frac{1}{\rho_{i}}) \\ &= n\prod_{i = 1}^{s}\frac{\rho_{i} - 1}{\rho_{i}} \end{align*} $$
欧拉定理
定义
- 若$\gcd(a, n) = 1$，则$a^{\varphi(n)} \equiv 1\kern2pt (mod \kern2pt n)$。
证明
- 设$S = \{\rho_1,\rho_2, \dots, \rho_{\varphi}\}，(\rho,n) = 1$。设$T = \{a\rho_1,a\rho_2, \dots, a\rho_{\varphi}\}，(a, n) = 1$。$T' = \{a\rho_1 \kern2pt mod\kern2pt n,a\rho_2 \kern2pt mod \kern2pt n, \dots, a\rho_{\varphi} \kern2pt mod \kern2pt n\}$。
要证明$T' = T$，需要满足三条件：1. $0 < T_i < n$；2. $T'$无重复元素；3.$(T'_i,n) = 1$。
条件1无需证明。
条件2等价于求证$T_i$不同余，我们可以通过反证法来证明。先假设$T_i$与$T_j$同余，即$a\rho_i \equiv a\rho_j \kern2pt (mod\kern2pt n)$。
$$ \because (a, n) = 1 \\ \therefore \rho_i \equiv \rho_j \kern2pt (mod \kern2pt n) $$
与$s$的定义矛盾，所以假设条件不成立，原条件成立。
条件3由原条件可得$T_i$与$n$互质
$$ \therefore (\rho_i, n) = 1 \\ \because (a, n) = 1 \\ \therefore (a\rho_i, n) = 1 $$
$$ \rho_1 \cdot \rho_2 \cdot \dots \cdot \rho_{\varphi} = a\rho_1 \cdot a\rho_2 \cdot \dots \cdot a\rho_{\varphi} \\ \Downarrow \\ \rho_1 \cdot \rho_2 \cdot \dots \cdot \rho_{\varphi} \equiv a\rho_1 \cdot a\rho_2 \cdot \dots \cdot a\rho_{\varphi} \kern2pt (mod \kern2pt n) \\ \because (S_i, n) = 1 \\ \therefore 1 \ \equiv a^{\varphi(n)} \kern2pt (mod \kern2pt m) $$
例题
2011 AMC 10B - 23
$2011^{2011}$的百位数字是什么？
(A) 1 (B) 4 (C) 5 (D) 6 (E) 9
解题思路
- 因为只需要百位数字，对$2011^{2011} \kern2pt (mod \kern2pt 1000) = 11^{2011}$。
$$ \because 11^{\varphi(1000)} \equiv 1 \kern2pt (mod \kern2pt 1000), \varphi(1000) = 400 \\ \therefore 11^{2011} \equiv 11^{11} \kern2pt (mod \kern2pt 1000) \\ \because 11^{11} = (10 + 1)^{11} = 1^{11} + 1 ^ {10} \cdot 10 \cdot C_{11}^{10} + 1^9 \cdot 100 \cdot C_{9}^{11} + \dots (超过百位无需计算) \\ \therefore 11^{11} \kern2pt (mod \kern2pt 1000) = (1 + 110 + 5500) \kern2pt (mod \kern2pt 1000) = 611 $$
- 选D