費馬小定理

費馬小定理 (Fermat's little theorem):$p$ 是質數、$p\nmid a$,則 $$a^{p-1}\equiv1\pmod p$$(另一種形式 $a^p\equiv a\pmod p$ 是它的推論,而且連 $p\mid a$ 也成立,所以對所有整數 $a$ 都對)。證明的一種方式:$a, 2a, \dots, (p-1)a$ 在模 $p$ 下是 $1,\dots,p-1$ 的重排,相乘後約掉 $(p-1)!$。

兩大用途:(1) 算大冪——指數先對 $p-1$ 取餘:$3^{100}\bmod7$,$100 = 6\cdot16 + 4$,所以 $\equiv3^4 = 81\equiv4$;(2) 求模反元素 $a^{-1}\equiv a^{p-2}$。

它是 Lagrange 定理在群 $U(p)$ 的特例(元素的階整除群的階 $p-1$),推廣到合數就是歐拉定理。反過來用它可以快速「幾乎」判斷質數(Fermat 質數測試,Miller–Rabin 的前身),RSA 的正確性證明也直接依賴它。