---

费马小定理

定义

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

---

题目

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

做法

考虑用一招移花接木,将 $\sum_{i=1}^{2025} i*i!$ 化成 $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}$$ .