一、前言

  今天要讲的内容，是数论中一个非常著名的定理 —— 费马小定理。阅读之前请确保对 二分快速幂 和 欧拉函数 已经有了一定的了解。本文的内容较短，但是作为 $RabinMiller$ 大素数判定 有着重要的意义，所以打算单独拿出一个章节来讲，内容较为简单，适合打算放弃学习数论的小伙伴重新找回学习的动力和勇气。
  数论不像其它一些有趣的算法，可能对你没有很强的学习动力，但是所有数论的内容都是成体系的，任何一个公式的推导，可能都需要很强的前置知识，那么我们就把这些前置知识都学完，相信到那时候，任何一个数论题在你面前都易如反掌。

二、费马小定理

1、费马小定理定义

【定义1】对于任意素数 $p$，和正整数 $a$，且 $a$ 不是 $p$ 的倍数，则：$$a^{p-1}\equiv 1(modp)$$

2、费马小定理证明

• 我们在学习欧拉函数的时候，已经知道了欧拉定理，如下：
• $$a^{\varphi (n)}\equiv 1(modn)$$
• 当 $n$ 为 素数 $p$ 时，它的欧拉函数为 $\varphi (p)=p-1$，将它带入欧拉定理，得到：
• $$a^{p-1}\equiv 1(modp)$$
• 费马小定理，得证。
• 注：关于欧拉定理的详细证明过程，可以参考以下这一篇文章，有兴趣的读者建议本文阅读完毕再看：
• 夜深人静写算法（三十一）- 欧拉函数

三、素数判定和伪素数

1、素数判定

• 我们可以用费马小定理来做什么？
• 一个比较直观的想法就是：可以随机找几个和 $n$ 互素的 $a$，然后对它计算：
• $$a^{n-1}modn$$
• 如果结果都为 1，我们就可以认为 $n$ 是一个素数。
• 如果这个结论成立，那么素数判定的时间复杂度就变成了 $O(Clo{g}_{2}n)$，其中 $C$ 为常数，代表找 $C$ 个 $a$ 来做判定试验，$O(lo{g}_{2}n)$ 则为利用二分快速幂进行判定的时间复杂度。
• 以上假设成立吗？
• 答案是 否！

2、伪素数

• 事实上，费马小定理给出的是关于素数判定的 必要非充分 条件。
• 如果 $p$ 是素数，则 $a^{p-1}\equiv 1(modp)$；相反，如果 $a^{p-1}\equiv 1(modp)$，则不能推导出 $p$ 是素数。
• 原因是存在一些数 $q$，对于所有和 $q$ 互素的 $a$，都能满足 $a^{q-1}\equiv 1(modq)$，这样的数，我们称它为伪素数。
• 第一个伪素数是 341，由 萨鲁斯 在 1819 年提出。

四、费马小定理的应用

1、二分快速幂降幂

【例题1】 给出一个大整数 $n(1\le n\le 10^{100000})$，求：$$2^{n}mod1000000007$$

• 任何一个正整数都就可以表示成 $n=kx+m$ 的形式，其中 $x$ 为除数，$k$ 为商，$m$ 为余数，并且 $0\le m<x$；其中除数 $x$ 可以是任意非零整数。
• 为了公式看起来整洁，我们用 $p$ 来代替素数 $1000000007$，并且令 $x=p-1$ 那么根据费马小定理，有：
• $$2^{p-1}modp=1$$
• 原式就可以表示成：
• $$\begin{array}{rl}{2}^{n}modp& =2^{kx+m}modp\\ & =2^{k(p-1)+m}modp\\ & =(2^{k(p-1)}modp)\ast (2^{m}modp)modp\\ & =2^{m}modp\end{array}$$
• 这里的 $m=nmod(p-1)$，可以利用大数取余求解。求得的 $m\in [0,p-1)$，再利用二分快速幂求解上面的式子即可。

2、模 p 逆元

【例题2】给定素数 $p$ 和 正整数 $a$，求满足 $ax\equiv 1(modp)$ 的最小正整数 x，如果不存在返回 -1。

• 这个问题实际上是求正整数 $a$ 在 模$p$ 域上的逆元。
• 首先，当 $a$ 为 $p$ 的倍数时，$ax\equiv 0(modp)$，所以一定不存在，直接返回 -1；
• 否则，根据费马小定理，我们可以知道：
• $$a^{p-1}\equiv 1(modp)$$
• 则可以得到：
• $$a\times a^{p-2}\equiv 1(modp)$$
• 对比原式，就可以得到：
• $$x=a^{p-2}modp$$

3、Rabin-Miller 素数判定

• 对于一个很大的数 $n$（例如十进制表示有 $100$ 位），如果还是采用试除法进行判定，时间复杂度必定难以承受，目前比较稳定的大素数判定法是 拉宾-米勒（$RabinMiller$）素数判定。
• 判定过程用到了费马小定理，具体算法的推导和应用过程将在后续章节再进行展开讲解。

• 关于 费马小定理 的内容到这里就暂时结束了，主要还是运用这个定理，对模数是素数的幂式进行降幂操作，如果还有不懂的问题可以留言告诉作者或者添加作者的微信公众号。

• 本文所有示例代码均可在以下 github 上找到：github.com/WhereIsHeroFrom/Code_Templates

五、费马小定理相关题集整理