从一个式子说起
Last updated on December 28, 2024 pm
质数拆解?
不论你是否了解,咱最近买了个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:
- $n=1$:
$$2^{2^1}-1 = 2^2-1 = 3 = 2^1+1$$
Claim Proofed.- 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}}}$$
很有趣的是我还没有读到和这个式子等价的表述(也可能是我看得太少了?),没啥时间进一步发掘,在这里记录下。