关于伪素数递推性质的证明问询

问题：若$n$是模$2$的伪素数（即$n$在$\mathbb{Z}_n$中是关于2的伪素数），证明$N=2^n -1$也是模$2$的伪素数（即$N$在$\mathbb{Z}_N$中是关于2的伪素数）。

尝试过程：根据定义，$n$是关于2的伪素数意味着存在整数$k$，使得$2^{n-1} -1 = nk$。但不知道接下来该怎么推导。

别担心，咱们一步步拆解这个证明，核心就是用好伪素数的定义和指数运算的小技巧~

首先明确我们的目标：要证明$N=2^n -1$是模2的伪素数，就得满足两个核心条件：

• $N$是合数；
• $2^{N-1} \equiv 1 \pmod{N}$（符合费马小定理的形式）

先处理第一个条件：因为$n$是伪素数，所以$n$本身是合数（伪素数的定义就是满足费马条件的合数）。设$n = ab$，其中$a,b$都是大于1的整数，那：
$$2^n -1 = (2^a)b -1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + \dots + 1)$$
显然右边两个因子都大于1，所以$N$是合数，第一个条件轻松搞定。

接下来是关键的第二个条件：证明$2^{N-1} \equiv 1 \pmod{N}$。
先把$N-1$展开变形：
$$N-1 = (2^n -1) -1 = 2^n - 2 = 2(2^{n-1} -1)$$
根据题目给的条件，$n$是模2的伪素数，所以$2^{n-1} \equiv 1 \pmod{n}$，也就是存在整数$k$使得$2^{n-1} -1 = nk$。把这个代入上式，得到：
$$N-1 = 2nk$$

现在看$2^{N-1}$，把指数替换成上面的结果：
$$2^{N-1} = 2^{2nk} = (2ⁿ⁾{2k}$$
而我们知道$N=2^n -1$，所以$2^n = N + 1$，自然有$2^n \equiv 1 \pmod{N}$。把这个代入上式：
$$(2ⁿ⁾{2k} \equiv 1^{2k} \equiv 1 \pmod{N}$$

这样就满足了第二个条件！结合前面的结论，$N$是合数且满足$2^{N-1} \equiv 1 \pmod{N}$，所以$N$确实是模2的伪素数。

其实你已经拿到了最关键的起始式子$2^{{n-1}-1=nk$，只要把$N-1$用这个式子关联起来，再利用$2}n \equiv 1 \pmod{N}$这个直观的关系，就能顺理成章推出来啦~

备注：内容来源于stack exchange，提问作者IcedTea