费马小定理是数论中一个非常重要的定理，它指出：如果 \( p \) 是一个质数，\( a \) 是一个整数且 \( a \) 与 \( p \) 互质，那么 \( a^{p-1} \equiv 1 \ (\text{mod} \ p) \)。
### 证明过程
1. **考虑集合**：
设 \( S = \{a, 2a, 3a, \ldots, (p-1)a\} \)。因为 \( a \) 和 \( p \) 互质，所以这个集合中的每个元素模 \( p \) 都是不同的，即它们构成了从 1 到 \( p-1 \) 的一个排列。
2. **乘积计算**：
将集合 \( S \) 中的所有元素相乘，得到：
\[
P = a \cdot 2a \cdot 3a \cdots (p-1)a = a^{p-1} \cdot (p-1)!
\]
另一方面，由于这些元素模 \( p \) 是 1 到 \( p-1 \) 的一个排列，它们的乘积也等于 \( (p-1)! \)：
\[
P \equiv (p-1)! \ (\text{mod} \ p)
\]
3. **比较两个表达式**：
因此，我们有：
\[
a^{p-1} \cdot (p-1)! \equiv (p-1)! \ (\text{mod} \ p)
\]
由于 \( (p-1)! \) 和 \( p \) 互质（因为 \( p \) 是质数），我们可以两边同时除以 \( (p-1)! \)，得到：
\[
a^{p-1} \equiv 1 \ (\text{mod} \ p)
\]
### 结论
这样我们就证明了费马小定理：如果 \( p \) 是一个质数，\( a \) 是一个整数且 \( a \) 与 \( p \) 互质，那么 \( a^{p-1} \equiv 1 \ (\text{mod} \ p) \)。
2 个回答
费马小定理的证明可以通过数论中的拉格朗日定理来完成。拉格朗日定理指出，对于任意有限群G和元素g∈G，g的阶（即g^n=e的最小正整数n）必须整除G的阶。在模p的情况中，我们可以将整数集Z_p看作一个群，其中加法运算定义为模p的和。由于p是质数，所以Z_p的阶为p。
现在考虑集合A = {1, 2, ..., p-1}，这是小于p的正整数集合。我们想要找到一个元素a∈A，使得a^(p-1) ≡ 1 (mod p)。如果存在这样的a，那么根据拉格朗日定理，a的阶必须整除p-1。但是p-1是质数p的因子，所以a的阶只能是1或者p-1。
如果a的阶是1，那么a = 1，此时a^(p-1) = 1^(p-1) = 1，满足条件。
如果a的阶是p-1，那么对于任意1 ≤ i ≤ p-2，都有a^i ≠ 1 (mod p)，因为这将意味着a的阶小于p-1，与我们的假设矛盾。因此，a^(p-1) ≡ 1 (mod p)。
综上所述，我们证明了费马小定理：如果p是一个质数，a是一个整数且a与p互质，那么a^(p-1) ≡ 1 (mod p)。