是否存在无穷多正整数n,使得n整除((2^n)-2)

Question

是否存在无穷多正整数n,使得n整除((2^n)-2)

Answer 1

这样的合数n称为以2为底的伪质数.
以2为底的伪质数是有无穷多的, 可以用如下结论构造:
若n是一个以2为底的伪质数, 则2^n-1也是以2为底的伪质数.
证明: 首先由n是合数, 2^n-1也是合数 (若k | n, 则2^k-1 | 2^n-1).
由n | 2^n-2, 可设2^n-2 = n·N.
2^n除以2^n-1余1, 故2^(2^n-2) = (2^n)^N除以2^n-1也余1.
于是2^(2^n-1)除以2^n-1余2, 即2^n-1 | 2^(2^n-1)-2.
即2^n-1也是以2为底的伪质数.
根据上面的结论, 只需要给出一个以2为底的伪质数, 就能构造无穷多个.
最小的例子是341 = 11·31, 因为341 | 1023 = 2^10-1, 即2^10除以341余1,
所以2^340 = (2^10)^34也除以341余1, 341 | 2^340-1, 故341 | 2^341-2.
于是可得到一列以2为底的伪质数: 341, 2^341-1, 2^(2^341-1)-1, 2^(2^(2^341-1)-1)-1,...
如果觉得341来得比较突兀, 也可以用这个结论:
若p为质数, 但2^p-1不是质数, 则2^p-1是以2为底的伪质数.
证明已经包含在前面的证明中了.
依次尝试p = 2, 3, 5, 7, 11,...得到2^11-1 = 2047 = 23·89是以2为底的伪质数.
可得另外一列以2为底的伪质数: 2047, 2^2047-1,2^(2^2047-1)-1,...