从一个式子说起

质数拆解？

不论你是否了解，咱最近买了个Casio fx-991CN X函数计算器。
功能很强大，不得不否认。但特别引起我注意的一个是FACT（Factorization）功能。
常年学密码学的elf自然会整各种各样的数做质数拆解玩，有这么一个功能自然是很方便的。但是，在拆解几个特殊的数的时候，一个似曾相识的规律浮出了水面：

$$
3 = (2+1)
$$
$$
15 = 3\times5 = (2+1)(4+1)
$$
$$
255 = 3\times5\times17 = (2+1)(4+1)(16+1)
$$
$$
65535 = 3\times5\times17\times257 = (2+1)(4+1)(16+1)(32+1)
$$

简单归纳下：
$$
2^{2^n}-1 = (2^1+1)(2^2+1)\dots(2^{2^{n-1}}+1)
$$

Proof. (Using Mathmatical induction)

We suppose that:

1. $n=1$:
   $$2^{2^1}-1 = 2^2-1 = 3 = 2^1+1$$
   Claim Proofed.
2. Suppose the equation hold when $n=k$, where $k\in\mathbb{N}^\ast$
   $$2^{2^n}-1 = (2^1+1)(2^2+1)\dots(2^{2^{n-1}}+1)$$
   Thus the equation must hold when $n=k+1$
   Thus:
   $$2^{2^{k+1}}-1=2^{2k\times2}-1=2^{(2k)\times2}-1=2^{2k^2}-1=(2^{2^k}-1)(2^{2^k}+1)=2^{2^n}-1 = (2^1+1)(2^2+1)\dots(2^{2^{k-1}}+1)(2^{2^k}+1)$$
   Which is surely still hold.
   Claim Proofed.

Thus, for any $n\in\mathbb{N}^\ast$, the equation would hold.

素数和费马？

如果你了解数论的话，你会发现$2^{2^n}-1$跟一个形式很相似：

a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form $F_{n}=2^{2^{n}}+1$ where $n$ is a non-negative integer. ——Wikipedia, Fermat number

很显然，我们上述的式子可以改写成如下：
$$2^{2^n}-1=F_{1}F_{2}\dots F_{n-1}$$
或者用同余式：
$$2^{2^n}\equiv1{\pmod {F_{1}F_{2}\dots F_{n-1}}}$$
也就是：
$$2^{2^n}\equiv1{\pmod {F_{n}}}$$

---

很有趣的是我还没有读到和这个式子等价的表述（也可能是我看得太少了？），没啥时间进一步发掘，在这里记录下。