假设 p 是质数 且 gcd(a, p) = 1 ， 那么 a^{p - 1} \equiv 1
证明：
- 构建 p 的完全剩余系 P = {1,2,3,4,5,…,p-1} (完全剩余系的定义：关于一个集合，其中的数 \mod{} 一个自然数 p 覆盖所有余数称为完全剩余系 )
- 根据剩余系定理（ gcd(b,m) = 1 那么 M = {b \times a_1, b \times a_2, b \times a_3,…,b \times a_m} 是关于 m 的完全剩余系 ） 则集合 A = {a, 2a, 3a,…,(p - 1)a} 是关于 p 的完全剩余系。
- 令 W = 1 \times 2 \times 3 \times … \times (p - 1) 则 W \equiv W （显而易见） A 集合的乘积为 a \times 2a \times 3a \times 4a …… \times (p - 1)a = a ^ {p - 1} \times W 由于 A 是关于 p 的完全剩余系， 其乘积 Y 满足： Y \equiv W
- 根据同余约减定理 a^{p - 1} \times W \equiv W \Longrightarrow a^{p - 1} \equiv 1