跳转至

费马小定理

费马小定理

若 p为素数， \gcd(a, p) = 1，则 a^{p - 1} \equiv 1 \pmod{p}。

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

欧拉定理

若 \gcd(a, m) = 1，则 a^{\phi(m)} \equiv 1 \pmod{m}。

证明

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

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

扩展欧拉定理

a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p

证明

证明转载自synapse7

  1. 在 a的 0次， 1次，。。。， b次幂模 m的序列中，前 r个数（ a^0到 a^{r-1}) 互不相同，从第 r个数开始，每 s个数就循环一次。

    证明：由鸽巢定理易证。

    我们把 r称为 a幂次模 m的循环起始点， s称为循环长度。（注意： r可以为 0）

    用公式表述为： a^r\equiv a^{r+s}\pmod{m}

  2. a为素数的情况

    令 m=p^rm'，则 \gcd(p,m')=1，所以 p^{\phi(m')}\equiv 1\pmod{m'}

    又由于 \gcd(p^r,m')=1，所以 \phi(m') \mid \varphi(m)，所以 p^{\varphi(m)}\equiv 1 \pmod {m'}，即 p^\phi(m)=km'+1，两边同时乘以 p^r，得 p^{r+\phi(m)}=km+p^r（因为 m=p^rm'）

    所以 p^r\equiv p^{r+s}\pmod m，这里 s=\phi(m)

  3. 推论： p^b\equiv p^{r+(b-r) \mod \phi(m)}\pmod m

  4. 又由于 m=p^rm'，所以 \phi(m) \ge \phi(p^r)=p^{r-1}(p-1) \ge r

    所以 p^r\equiv p^{r+\phi(m)}\equiv p^{r \mod \phi(m)+\phi(m)}\pmod m

    所以 p^b\equiv p^{r+(b-r) \mod \phi(m)}\equiv p^{r \mod \phi(m)+\phi(m)+(b-r) \mod \phi(m)}\equiv p^{\phi(m)+b \mod \phi(m)}\pmod m

    即 p^b\equiv p^{b \mod \phi(m)+\phi(m)}\pmod m

  5. a为素数的幂的情况

    是否依然有 a^{r'}\equiv a^{r'+s'}\pmod m？（其中 s'=\phi(m),a=p^k)

    答案是肯定的，由 2 知 p^s\equiv 1 \pmod m'，所以 p^{s \times \frac{k}{\gcd(s,k)}} \equiv 1\pmod {m'}，所以当 s'=\frac{s}{\gcd(s,k)}时才能有 p^{s'k}\equiv 1\pmod {m'}，此时 s' \mid s \mid \phi(m)，且 r'= \lceil \frac{r}{k}\rceil \le r \le \phi(m)，由 r',s'与 \phi(m)的关系，依然可以得到 a^b\equiv a^{b \mod \phi(m)+\phi(m)}\pmod m

  6. a为合数的情况

    只证 a拆成两个素数的幂的情况，大于两个的用数学归纳法可证。

    设 a=a_1a_2,a_i=p_i^{k_i}， a_i的循环长度为 s_i；

    则 s \mid lcm(s_1,s_2)，由于 s_1 \mid \phi(m),s_2 \mid \phi(m)，那么 lcm(s_1,s_2) \mid \phi(m)，所以 s \mid \phi(m)， r=\max(\lceil \frac{r_i}{k_i} \rceil) \le \max(r_i) \le \phi(m)；

    由 r,s与 \phi(m)的关系，依然可以得到 a^b\equiv a^{b \mod \phi(m)+\phi(m)}\pmod m；

    证毕。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论