费马小定理

huangjf · 2022-09-10 01:11:00 · 算法·理论

1、概述

若 p 是质数且 a\bot p，则 a^{p-1} \equiv 1 \pmod{p}。

变式 a^b \bmod p = a^{b \bmod (p-1)} \bmod p。

当 p 为质数，且 a\bot p 时：

$\therefore \{a,2a,3a,\dots,(p-1)a\}$ 也为模 $p$ 的简化剩余系。 $\therefore a \cdot 2a \cdot 3a\dots(p-1)a \equiv (p-1)! \cdot a^{p-1} \equiv (p-1)! \pmod{p}

\because (p-1)! \perp p

\therefore$ 可以将 $(p-1)!$ 消去，即 $a^{p-1} \equiv 1 \pmod{p}