费马小定理：秒算 2 的百万次方模 7

题目

不用算 $2^{100}$ 到底多大，求它除以 7 的余数。

答案与解析

用费马小定理：若 $p$ 是素数、$a$ 与 $p$ 互素，则 $a^{p-1} \equiv 1 \pmod p$

取 $a=2,\ p=7$（7 是素数，2 不被 7 整除），得 $2^{6} \equiv 1 \pmod 7$

于是把指数按 6 分组： $2^{100} = 2^{6\times16 + 4} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 16 \equiv 2 \pmod 7$

答案：余数是 2。

背后的数学

费马小定理是现代公钥密码（RSA）的基石之一，它让我们可以在“模大素数”的世界里安全地处理超大指数。它的升级版是欧拉定理 $a^{\varphi(n)}\equiv1\pmod n$（$\varphi$ 为欧拉函数），而更深的推广则是群论里的拉格朗日定理——幂等归一的循环，本就是群结构的回声。