费马小定理例题讲解-费马小定理例题详解

费马小定理：不整除的馀数之谜 咱们今天聊个有点“玄乎”但数学里却特别“硬核”的定理。费马小定理，听起来像是个背公式就能拿分的小菜，但实际上，它处理的对象可不是一般/平平的整数，而是质数。
要是你拿个一般/平平的大数去取模，那可能是天书；但一旦碰上了质数，这事儿就变了味，变得好办多了。 先说点反面教材。大量人一听到“整除”，脑子里浮现的画面是 $7$ 除 $49$，结局等于 $7$，整除符号亮起。
这就对了，但费马小定理有个前提，那就是“互质”。
也就是说，这个数不能是 $7$ 的倍数。
要是 $a$ 本身就是质数 $p$，那它肯定整除 $p$，根本没法取模，更别取模等于 $1$ 了。
要是 $a$ 是合数，比如 $49$ 和 $p=7$，那 $49$ 必然被 $7$ 整除，结局更是 $0$。
只有当 $a$ 和 $p$ 互质的时候，结局才可能一神似 $1$。
这时候，我们要推翻直觉，验证那个看似荒谬的 $1$。 举个最直接的例子。假设我们要算 $12$ 除以质数 $7$ 的余数。$12 div 7$，商是 $1$，余数是 $5$。
这数论里这叫同余。但要是我们换个思路，看看能不能通过费马小定理来“验证”这个结局，这就有趣了。 这里有个小技巧，叫“替换”。
要是我们把 $a$ 换成 $a^2$，那 $a^2 pmod p$ 的结局会直接翻倍（在数值上）。
比如 $a=12, p=7$，$a^2=144$。$144$ 除以 $7$，商是 $20$，余数是 $4$。
这一跳，从 $5$ 变成了 $4$。
这就意味着，$a equiv -a^2 pmod p$。
这个关系听起来挺怪，但逻辑上彻底成立。 目前，我们直接套用费马小定理的结论。
既然 $a$ 和 $p$ 互质，那么 $a^{p-1}$ 能被 $p$ 整除。用同余记号写出来，就是 $a^{p-1} equiv 1 pmod p$。代入我们刚刚那个思路，$a = 12, p = 7$。$p-1$ 是 $6$。
故此 $12^6 equiv 1 pmod 7$。 这时候，让我们看看幂次增长的情况。$12 equiv 5 pmod 7$。
那么 $12^6 equiv 5^6 pmod 7$。持续算下去，$5^2 = 25 equiv 4 equiv -3 pmod 7$。$5^3 = 125 equiv 6 equiv -1 pmod 7$。
只要把指数变成 $6$，就是 $(-1)^2 = 1$。逻辑闭环了。
这时候，我们算出了 $12^6$ 除以 $7$ 的余数是 $1$。 这就验证了费马小定理：$a^{p-1} equiv 1 pmod p$。 实际上，这个定理不只是是验证整除性，它更像是一个强大的工具，用来解决那些本来该让人抓狂的整除难题。想象一下，你需求算一个模 $p$ 下的数值，而 $a$ 本身挺大，要么 $a$ 和 $p$ 的关系挺复杂，直接算 $a^{p-1}$ 得用两次大数运算，在大数运算里这绝对是灾难。费马小定理脑洞一开，$p-1$ 变小了，难题就迎刃而解了。 再来看一个略微“绕一点”的例子。假设我们要算 $a^{2^{p-1}} equiv 1 pmod p$，要是 $a$ 够大，这实际上是个超大的幂次运算。费马小定理告诉我们，$a^{p-1}$ 就是那个基础的余数 $1$。便，$(a^{p-1})^{2^{p-1}}$ 就等于 $1^{2^{p-1}}$，也就是 $1$。 这就解释了一个挺常见的数论现象。
比方说，当 $p=17$ 时，$p-1=16$。任何不整除 $17$ 的数 $a$，它的 $16$ 次方模 $17$ 都等于 $1$。
这个 $16$ 次方，实际上就是 $2^4$。
故此 $a^{16} equiv 1 pmod{17}$。
要是 $a$ 挺大，比如 $a = 1000000000000000003$（随意编个大的），只要它不被 $17$ 整除，我们实际上不用算那 $10^{18}$ 这个数，直接利用 $a equiv 5 pmod{17}$，$5^{16} equiv 1 pmod{17}$，算出余数就是 $1$。 这在实际应用里意味着啥？意味着我们能够用指数对数要么离散对数等工具去处理庞大的数字，把复杂度从 $O(n)$ 降到接近 $O(log n)$。在密码学里，RSA 算法的核心就是基于这个定理。生成密钥时，把多个大质数相乘拿到一个 $n$，然后对 $n-1$ 进行鲍莫尔因子分解（Baby-step Giant-step），通过寻找 $a^b equiv 1 pmod n$ 的解，就能快速还原出 $a$。 自然，费马小定理有个致命的“陷阱”。
要是 $a$ 是 $p$ 的倍数，比如 $a=2p$，那 $a^{p-1} equiv 0 pmod p$，一辈子取不出 $1$。
故此，用这个定理前，务必第一步先确认“互质”。
这是它最本质的要求，一旦跳过这一步，整个后果就是毁灭性的。 最终，我们回到最好办的例子 $p=7, a=12$。验证过程：$12 equiv 5$，$5^2 equiv 4$，$5^3 equiv 6 equiv -1$，$5^6 equiv (-1)^2 = 1$。结局吻合。
这说明，只要 $a$ 和 $p$ 互质，幂次 $p-1$ 这个神秘数字，确实只负责把余数锁定在 $1$。 费马小定理之故此迷人，是出于它打破了我们对大数运算的常规认知。它告诉我们，有些看似无法处理的庞大数字，在质数的约束下，其内在结构却贼好办，就连能够用好办的同余关系去“撬动”。下次再遇到大数取模的难题，不妨先甩出 $p-1$，看看能不能简化难题。
这不仅是数学的优雅，更是工程上解决实际难题的利器。
毕竟，在数学的世界里，有时候最好办的公式，就是最强的武器。