2. 假设 GCD(2^m-1, 2^n-1) = s > 1.

则 s+1 整除 2^m, s-1 整除 2^n. 为什么？
得 s = 2^a-1 = 2^b + 1, 2^a = 2*(2^(b-1)+1)
得 b = 1 即 s = 3.
于是 3 必须整除 2^m-1=2^(2*k+1)-1 = 2*4^k-1.

用归纳法证明 3 不能整除 2*4^k-1：
k = 1 显然。
假定 3 不能整除 2*4^t-1 而整除
2*4^(t+1)-1 = 2*4*4^t-4+3 = 4*（2*4^t-1)+3
矛盾。


取 m=11，2^11 - 1 = 2047 = 23x 89;
但是 89 + 1 = 90 不是 2 的任何此方。

锟斤拷锟洁辑时锟斤拷: 2023-08-31 03:19:22