费马小定理

定义

若 pp 为素数, gcd(a,p)=1\gcd(a, p) = 1 ,则 a^{p - 1} \equiv 1 (\mod p) . 另一种形式: 对于任意整数 aa ,有 a^p \equiv a (\mod p) .

题目

求 3^{\sum_{i=1}^{2025} i \cdot i!} \mod 101 .

做法

考虑用一招移花接木,将 ∑i=12025i∗i!\sum_{i=1}^{2025} i*i! 化成 100n+p(p<100)100n + p (p < 100) 的形式,有

3^{\sum_{i=1}^{2025} i \cdot i!} = 3^{100n} \cdot 3^p$$ . 由费马小定理,得 $$3^{100n} \equiv 1 (\mod 101)$$ . 故 $$3^{100n} \cdot 3^p \equiv 3^p$$ . 下求 $p$ ,即求 $\sum_{i=1}^{2025} i \cdot i! \mod 100$ . 因为 $$i \cdot i! = (i + 1 - 1) \cdot i! = (i + 1)! - i!$$ . 所以 $$\begin{align} \sum_{i=1}^{2025} i \cdot i! = (2! - 1!) + (3! - 2!) + \cdots + (2026! - 2025!) \\ = 2026! - 1 \end{align}$$ . 因为 $2026!$ 必定是 $100$ 的倍数, 所以 $$2026! - 1 \equiv 2026! + 99 \equiv 99 (\mod 100)$$ . 即 $p = 99$ . 所以, 由费马小定理, 有 $$\begin{align} 3^{\sum_{i=1}^{2025}i \cdot i!} \equiv 3^{99} \\ \equiv 3^{99} \cdot 102 \\ = 3^{100} \cdot 34 \\ \equiv 34 (\mod 101) \end{align}$$ .