数论（9）：费马小定理与欧拉定理- Koshkaaa

费马小定理与欧拉定理

费马小定理： 当 $m$ 为质数且 $a$ 不为 $m$ 的倍数（即： $gcd(a,m) = 1$ 时有 $a^{m−1}≡1\ mod\ (m) $

另一个形式：对于任意整数 $a$ ，有 $a^m \equiv a \pmod{m}$ 。

根据费马小定理可知： $a^{m−2}$ 就是 $a$ 在模 $m$ 意义下的逆元.

欧拉定理： 当 $a$ , $m$ 互质时, $aϕ(m)≡\ 1\ mod\ (m)$ （这个式子也可以求逆元）

其实根据欧拉函数，我们可以看出费马小定理就是欧拉定理的特殊情况，因为若 $m$ 为质数：$ ϕ(m)=m−1$

简单来说欧拉函数 φ(n) 是小于等于 n 的正整数中与 n 互质的数的个数。

费马小定理证明

设一个质数为 $p$ ，我们取一个不为 $p$ 倍数的数 $a$ 。

构造一个序列： $A=\{1,2,3\dots,p-1\}$ ，这个序列有着这样一个性质：

\[\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p \]

证明：

\[\because (A_i,p)=1,(A_i\times a,p)=1 \]

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 $A_i$ )

设 $f=(p-1)!$ , 则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p$

\[a^{p-1}\times f \equiv f \pmod p \\ a^{p-1} \equiv 1 \pmod p \]

证毕。

首先看一个基本的例子。

令 $a = 3，n = 5$ ，这两个数是互素的。

比 $5$ 小的正整数中与 $5$ 互素的数有 $1、2、3和4$ ，所以 $φ(5)=4$ 。

计算: $a^{φ(n)} = 3^4 =81$ ，而 $81= 80 + 1 ≡ 1 （mod\ 5）$ 。

与定理结果相符。

简化幂的模运算

这个定理可以用来简化幂的模运算。

比如计算 $7^{222}$ 的个位数，实际是求7 $^{222}$ 被 $10$ 除的余数。

$7$ 和 $10$ 互素，且 $φ(10)=4$ 。

由欧拉定理知 $7^4≡1\ (mod\ 10)$ 。

所以 $7^{222}=(7^4)^55*(7^2)≡1^{55}*7^2≡49≡9\ (mod\ 10)$ 。

欧拉定理证明

实际上这个证明过程跟上文费马小定理的证明过程是非常相似的： 构造一个与 $m$ 互质的数列 ，再进行操作。

设 $r_1, r_2, \cdots, r_{\varphi(m)}$ 为模 $m$ 意义下的一个简化剩余系，则 $ar_1, ar_2, \cdots, ar_{\varphi(m)}$ 也为模 $m$ 意义下的一个简化剩余系。所以 $r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}$ ，可约去 $r_1r_2 \cdots r_{\varphi(m)}$ ，即得 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。

当 $m$ 为素数时，由于 $\varphi(m) = m - 1$ ，代入欧拉定理可立即得到费马小定理。

Wiki： https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86

费马小定理、欧拉定理与扩展欧拉定理（含证明）

数论四大定理之欧拉定理

RSA算法原理（一）之欧拉定理