如何找到含7个[10^7,10^9]素因子的Carmichael数？

尝试的解决方法 #

Chernick公式 #

使用7因子形式的Chernick公式构造候选数：
M(m) = (6m+1)(12m+1)(18m+1)(36m+1)(72m+1)(144m+1)(288m+1)
需满足两个条件：

• 公式中所有因子均为素数
• 参数m能被8整除

Korselt准则 #

验证候选数是否为Carmichael数的核心依据：一个正合数n是Carmichael数当且仅当：

• n无平方因子
• 对n的每一个素因子p，(n-1)能被(p-1)整除

实现代码 #

from gmpy2 import is_prime
from math import prod

m = 1666672
while True:
    x = [i * m + 1 for i in [6, 12, 18, 36, 72, 144, 288]]
    n = prod(x)
    if all(is_prime(i) and (n - 1) % (i - 1) == 0 and i in range(10 ** 7, 10 ** 9 + 1) for i in x):
        print(m, n)
        break
    elif x[6] > 10 ** 9:
        print('Nothing found')
        break
    m += 8

结果与问题 #

运行代码后得到：

• m = 18726360
• n = 112504155402956714375844566364658214310419726067438239203656961

n的素因子为：112358161、224716321、337074481、674148961、1348297921、2696595841、5393191681

但其中仅前4个素因子落在[10^7, 10^9]范围内，不符合题目要求。

内容的提问来源于stack exchange，提问作者E-One