费马小定理【Fermat's little theorem】

2021-01-27 本文已影响0人摇摆苏丹

表述

设 $p$ 为素数， $a$ 是任意整数且 $p \nmid a$ ，则 $a^{p-1} \equiv 1 (mod \ p)$ 。

证明

先证明一个引理：设 $p$ 为素数， $a$ 是任意整数且 $p \nmid a$ ，则序列 $A = a,2a,3a,\cdots,(p-1)a$ 与序列 $B = 1,2,3,\cdots,(p-1)$ 在模 $p$ 且忽略顺序的情况下相等。
从序列 $A$ 中任取两个数 $ja,ka$ ，并假设有 $ja \equiv ka \ (mod \ p)$ ，即 $p \mid (j-k)a$ 。由 $p \nmid a$ ，得到 $p \mid j-k$ 。对 $j,k$ 显然有 $1 \leq j,k \leq p-1$ ，那么 $|j-k| \lt p-1$ 。小于 $p-1$ 且能被 $p$ 整除的数只能是0，因此得到 $j=k$ ，也就是说，序列 $A$ 中不存在两个元素在模 $p$ 意义下相等，即序列 $A$ 中所有元素在模 $p$ 意义下都不相等。
序列 $A$ 中各个元素模 $p$ 只能获得序列 $B$ ，此时引理得证。
根据引理，有 $A=B$ 。将方程两边分别累乘，得到：
$\begin{array}{c} a·2a·3a·\cdots·(p-1)a \equiv 1·2·3·\cdots·(p-1) \ (mod \ p)\\ a^{p-1}(p-1)! \equiv (p-1)! \ (mod \ p) \end{array}$
$(p-1)!$ 与 $p$ 互素，根据同余式的除法性质，费马小定理得证：
$a^{p-1} \equiv 1 \ (mod \ p)$

费马小定理【Fermat's little theorem】

表述

证明

猜你喜欢

热点阅读