费马小定理

佬头 · 2023-11-13 20:40:12 · 算法·理论

Description

费马小定理是数论中的一个重要定理：如果 p 是一个质数，而整数 a 不是 p 的倍数，则有 a^{(p-1)}\equiv1\pmod p。

Proof

引理 1

• 若 a,b,c 为任意 3 个整数，m为正整数，且 \gcd(m,c)=1，则当 ac\equiv bc\pmod m 时，有 a\equiv b\pmod m。

  证：

  由 ac\equiv bc\pmod m 得 ac-bc\equiv0\pmod m，即 (a-b)c\equiv0\pmod m。

  由于 \gcd(m,c)=1，则 a-b\equiv0\pmod m，即 a\equiv b\pmod m。

引理 2

• 设 m 是一个整数且 m\gt1，b 是一个整数且 \gcd(m,b)=1。如果 a_1,a_2,a_3,\dots,a_m 是模 m 的一个完全剩余系，则 ba_1,ba_2,ba_3,\dots,ba_m 也构成模 m 的一个完全剩余系。

  证：

  设 \exists~1\le i,j\le m,~ba_i\equiv ba_j\pmod m。

  因为 \gcd(m,b=1)，则由引理 1 得 a_i\equiv a_j\pmod m，与条件不符，假设不成立。

  则 ba_1,ba_2,ba_3,\dots,ba_m 构成模 m 的一个完全剩余系。

由于 p 是一个质数且 a 不是 p 的倍数，显然 \gcd(p,a)=1。

构造素数 p 的完全剩余系 1,2,\dots,p-1，则根据引理 2 得 a,2a,\dots,(p-1)a 也构成模 m 的一个完全剩余系。

由完全剩余系的性质得：

即：

易知 \gcd(p,(p-1)!)=1，则有 a^{p-1}\equiv1\pmod p。

证毕。