卢卡斯-卡米切尔数

卢卡斯-卡米切尔数（Lucas–Carmichael number）是数学中的一种正合数，得名自数学家爱德华·卢卡斯和罗伯特·丹尼·卡米切尔。若$n$为卢卡斯-卡米切尔数，则对于其所有素因数$p$，应有$p+1$是$n+1$的因数。

按习惯，卢卡斯-卡米切尔数必须为无平方数因数的数（即不能被任何素数的平方整除）。若不加上限制，则任何素数的立方$p^{3}$（如$2^{3}=8$与$3^{3}=27$）皆会因其唯一的素因数$p$满足恒等式： $$p^{3}+1=(p+1)(p^{2}-p+1),$$ 而使得$p+1$必能整除$p^{3}+1$，从而平凡地满足条件。

数值列表

卢卡斯-卡米切尔数的数列被记为 A006972，以下列出此数列的前几项与其素因数：

项次	数值	素因数1	素因数2	素因数3	素因数4	素因数5	素因数6
1	399	3	7	19
2	935	5	11	17
3	2015	5	13	31
4	2915	5	11	53
5	4991	7	23	31
6	5719	7	19	43
7	7055	5	17	83
8	8855	5	7	11	23
9	12719	7	23	79
10	18095	5	7	11	47
11	20705	5	41	101
12	20999	11	23	83
13	22847	11	31	67
14	29315	5	11	13	41
15	31535	5	7	17	53
16	46079	11	59	71
17	51359	7	11	23	29
18	60059	19	29	109
19	63503	11	23	251
20	67199	11	41	149
21	73535	5	7	11	191
22	76751	23	47	71
23	80189	17	53	89
24	81719	11	17	19	23
25	88559	19	59	79
26	90287	17	47	113
45	588455	5	7	17	23	43
—	50587199	11	19	29	59	83	89

注：8855（第8项）、588455（第45项）与50587199分别为首个具有4个、5个与6个素因数的卢卡斯-卡米切尔数。

性质

给定任何卢卡斯-卡米切尔数$n$，其必满足以下性质：

首先，$n$为奇数。

利用反证法证明

若$n$为偶数，由于$n$为合数且不能被素数的平方整除，其必具有素因数$2$及至少一个奇素因数$p$（即$2p\mid n$）。根据定义，应有$p+1\mid n+1$；然而此时$n+1$为奇数，而$p+1$为偶数，偶数不可能整除奇数，产生矛盾。故$n$为奇数。

再来，$n$至少有3个素因数。

利用反证法证明

若$n$仅有两个奇素因数（设$n=p_{1}p_{2}$，且$p_{1}<p_{2}$），根据定义，应有$p_{2}+1\mid p_{1}p_{2}+1$，即存在正整数$k$使得 $$p_{1}p_{2}+1=k(p_{2}+1).$$ 等号两侧模$p_{2}$同余，得 $$1\equiv k{\pmod {p_{2}}}.$$ 故$k$可能为$1,p_{2}+1,\dots$。又因$p_{1}p_{2}+1<(p_{2}+1)^{2}$，故必有$k=1$，导出$p_{1}=1$，与$p_{1}$为素数产生矛盾。故$n$至少有3个素因数。

最后，$n\geq 399$。

证明399为最小的卢卡斯-卡米切尔数

已知$n$为奇数，不被素数的平方整除，且至少有3个素因数。分别考虑以下情况：

1. 若${\boldsymbol {n}}$有4个以上素因数：$n\geq 3\times 5\times 7\times 11=1155>399$。

接着，设$n=p_{1}p_{2}p_{3}$（其中$p_{1}<p_{2}<p_{3}$）。根据定义，及以下等式 $$n+1=p_{2}p_{3}(p_{1}+1)-(p_{2}p_{3}-1),$$ 可知$p_{1}+1\mid n+1$等价于$p_{1}+1\mid p_{2}p_{3}-1$。同理，三数也须满足 $$p_{2}+1\mid p_{1}p_{3}-1,\quad p_{3}+1\mid p_{1}p_{2}-1.$$

2. 若${\boldsymbol {p_{1}=5}}$：最小组合为$5\times 7\times 11=385$，但其中$12\nmid 385$，故$n>5\times 7\times 13=455>399$。
3. 若${\boldsymbol {p_{1}=3,p_{2}\geq 11}}$：则$p_{3}\geq 13$，此时$n>3\times 11\times 13=429>399$。
4. 若${\boldsymbol {p_{1}=3,p_{2}=5}}$：由$p_{3}+1\mid p_{1}p_{2}-1=14$解得素因数$p_{3}=13$。但经检验得$5+1\nmid 3\times 13-1$，也就是$p_{2}+1\nmid p_{1}p_{3}-1$，而$3\times 5\times 13=195$不为卢卡斯-卡米切尔数。
5. 若${\boldsymbol {p_{1}=3,p_{2}=7}}$：由$p_{3}+1\mid p_{1}p_{2}-1=20$解得素因数$p_{3}=19$，此时$n=399$，也正好是个卢卡斯-卡米切尔数。

综上所述，$n\geq 399$，换句话说，399为最小的卢卡斯-卡米切尔数。

应用

卢卡斯-卡米切尔数在结构上与卡米切尔数呈现明确的正负号对偶关系，两者的定义皆可由科瑟尔特准则推导而出：

• 卡米切尔数：无平方数因数的合数$n$，对其所有素因数$p$均满足：$$p-1\mid n-1.$$

• 卢卡斯-卡米切尔数：无平方数因数的合数$n$，对其所有素因数$p$均满足：$$p+1\mid n+1.$$

如上两数于计算数论与素性测试中，常扮演着“测试陷阱”的角色。传统基于费马小定理的费马素数判定法会被卡米切尔数欺骗而误判为素数，而基于卢卡斯数列的卢卡斯素性检验则可能对特定的卢卡斯-卡米切尔数产生伪阳性结果。

为了克服单一测试的漏洞，数学家提出了结合强米勒-拉宾素性检验（基于费马小定理）与强卢卡斯素性检验（基于卢卡斯数列）的Baillie-PSW素性检验，是现代计算机科学中极为高效且可靠的概率性素性测试标准。

虽然至今仍未发现能同时欺骗这两种检验的“双重伪素数”，但其理论上的存在性仍作为数论中的一个开放问题，即：是否存在正合数$n$，对其每一个素因数$p$皆同时满足 $$p-1\mid n-1,\quad p+1\mid n+1.$$

参考

• PlanetMath （页面存档备份，存于互联网档案馆）