跳转至

阶 & 原根

前置知识:费马小定理欧拉定理拉格朗日定理

阶和原根,是理解模 m 既约剩余系 Zm 乘法结构的重要工具.基于此,可以定义 离散对数 等概念.更为一般的讨论可以参见抽象代数部分 群论环论 等页面相关章节.

本节中,总是假设模数 mN+ 和底数 aZ 互素,即 (a,m)=1,也记作 am

对于 nZ,幂次 anmodm 呈现一种循环结构.这个循环节的最小长度,就是 am 的阶.阶就定义为幂 anmodm 第一次回到起点 a0modm=1 时的指数:

对于 aZ,mN+am,满足同余式 an1(modm) 的最小正整数 n 称作 am 的阶(the order of a modulo m),记作 δm(a)ordm(a)

抽象代数 中,这里的「阶」就是模 m 既约剩余系关于乘法形成的群中,元素 a 的阶.用记号 δ 表示阶只适用于这个特殊的群.下面的诸多性质可以直接推广到抽象代数中群元素的阶的性质.

另外还有「半阶」的概念,在数论中会用 δ 记号表示.它是满足同余式 an1(modm) 的最小正整数.半阶不是群论中的概念.阶一定存在,半阶不一定存在.

幂的循环结构

利用阶,可以刻画幂的循环结构.对于幂 anmodm,可以将指数 n 对阶 δm(a) 做带余除法:

n=δm(a)q+r, 0r<δm(a).

进而,利用幂的运算律,就得到

an=aδm(a)q+r=(aδm(a))qarar(modm).

这说明,对于任意指数的幂,可以将它平移到第一个非负的循环节.由此,可以得到一系列关于阶的性质.

性质 1

对于 aZ,mN+am,幂次 a0(=1),a,a2,,aδm(a)1m 两两不同余.

证明

考虑反证.假设存在两个数 0i<j<δm(a),且 aiaj(modm),则有 aji1(modm).但是,0<ji<δm(a).这与阶的最小性矛盾,故原命题成立.

性质 2

对于 a,nZ,mN+am,同余关系 an1(modm) 成立,当且仅当 δm(a)n

证明

如前文所述,ananmodδm(a)(modm).由性质 1 可知,0r<δm(a) 中唯一一个使得 ar1(modm) 成立的 r 就是 r=0.因此,an1(modm),当且仅当 nmodδm(a)=0,也就是 δm(a)a

欧拉定理 中,同余关系 aφ(m)1(modm) 对于所有 am 都成立.结合性质 2,这说明对于所有 am,都有 δm(a)φ(m).换句话说,φ(m) 是所有 am 的阶的一个公倍数.对于一个正整数 m,所有 am 的阶 δm(a) 的最小公倍数,记作 λ(m),就是 mCarmichael 函数.后文会详细讨论它的性质.

和其他的循环结构类似,可以根据 a 的阶计算 ak 的阶.

性质 3

对于 k,aZ,mN+am,有

δm(ak)=δm(a)(δm(a),k).
证明

由性质 2,同余关系 (ak)n=akn1(modm) 成立,当且仅当 δm(a)kn.这一条件就等价于

δm(a)(δm(a),k)n.

使得这一条件成立的最小正整数就是

δm(ak)=δm(a)(δm(a),k).

乘积的阶

a,b 是与 m 互素的不同整数.如果已知阶 δm(a)δm(b),那么,同样可以获得一些关于它们乘积 ab 的阶 δm(ab) 的信息.

性质 4

对于 a,bZ,mN+a,bm,那么,有

[δm(a),δm(b)](δm(a),δm(b))δm(ab)[δm(a),δm(b)].
证明

因为 [δm(a),δm(b)]δm(a)δm(b) 的倍数,所以,由性质 2 可知

(ab)[δm(a),δm(b)]=a[δm(a),δm(b)]b[δm(a),δm(b)]1(modm).

再次应用性质 2,就得到

δm(ab)[δm(a),δm(b)].

这就得到右侧的整除关系.

反过来,由于

1(ab)δm(ab)δm(b)aδm(ab)δm(b)(modm),

所以,应用性质 2,就得到 δm(a)δm(ab)δm(b).两侧消去 (δm(a),δm(b)),就得到

δm(a)(δm(a),δm(b))δm(ab)δm(b)(δm(a),δm(b)).

消去公因子后,两个分式互素,这就得到

δm(a)(δm(a),δm(b))δm(ab).

同理,也有

δm(b)(δm(a),δm(b))δm(ab).

由于两个整除关系的左侧互素,有

[δm(a),δm(b)](δm(a),δm(b))=δm(a)δm(b)(δm(a),δm(b))2δm(ab).

这就得到左侧的整除关系.

对于 ab 的阶互素的情形,这一结论有着更为简单的形式.

性质 4'

对于 a,bZ,mN+a,bm,那么,有

δm(ab)=δm(a)δm(b)δm(a)δm(b).
证明

如果 δm(a)δm(b),那么性质 4 中所有整除关系都是等式,所以有

δm(ab)=[δm(a),δm(b)]=δm(a)δm(b).

反过来,如果 δm(ab)=δm(a)δm(b),那么根据性质 4,就有

δm(a)δm(b)=δm(ab)[δm(a),δm(b)].

这立马说明 (δm(a),δm(b))=1,即 δm(a)δm(b)

一般情形中,性质 4 得到的界已经是紧的.乘积的阶取得下界的情形很容易构造:例如 (a,b,m)=(3,5,7) 时,δm(a)=δm(b)=6,但是它们的乘积的阶 δm(ab)=1

尽管一般情形中,乘积 ab 的阶未必是它们的阶的最小公倍数,但是总能找到一个元素使得它的阶等于这个最小公倍数.

性质 5

对于 a,bZ,mN+a,bm,总是存在 cZcm 使得

δm(c)=[δm(a),δm(b)].
证明

考虑素因数分解:

δm(a)=ppαp, δm(b)=ppβp.

利用 αpβp 的大小关系,可以将所有素因子分为两类:

A={p:αpβp}, B={p:αp<βp}.

由此,分别设

γA=pApαp, γB=pBpαp, ηA=pApβp, ηB=pBpβp,

就有 δm(a)=γAγBδm(b)=ηAηB.根据性质 3,可知

δm(aγB)=δm(a)(δm(a),γB)=δm(a)γB=γA,δm(bηA)=δm(b)(δm(b),ηA)=δm(b)ηA=ηB.

因为 γAηB,由性质 4',就有

δm(aγBbηA)=γAηB=ppmax{αp,βp}=[δm(a),δm(b)].

因此,c=aγBbηA 就是阶为 [δm(a),δm(b)] 的元素.

这一结论常用于构造出指定阶的元素.

原根

原根是一些特殊元素——它的阶就等于所有模 m 既约剩余系的个数.

原根

对于 mN+,如果存在 gZgm 使得 δm(g)=|Zm|=φ(m),就称 gm 的原根(primitive root modulo m).其中,φ(m)欧拉函数

并非所有正整数 m 都存在模 m 的原根.由上文的性质 1,如果模 m 的原根 g 存在,那么,g,g2,,gφ(m) 所在的同余类互不相同,构成模 m 既约剩余系.特别地,对于素数 p,余数 gimodp 对于 i=1,2,,p1 两两不同.

抽象代数 中,原根就是循环群的生成元.这个概念只在模 m 既约剩余系关于乘法形成的群中有「原根」这个名字,在一般的循环群中都称作「生成元」.并非每个模 m 既约剩余系关于乘法形成的群都是循环群,存在原根就表明它同构于循环群,如果不存在原根就表明不同构.

模为 1 时,模 1 整数乘法群就是 {0}.这显然是循环群,所以原根就是 0

原根判定定理

如果已知模数 φ(m) 的全体素因子,那么很容易判断模 m 的原根是否存在.

定理

对于整数 m3gm,那么,g 是模 m 的原根,当且仅当对于 φ(m) 的每个素因数 p,都有

gφ(m)p1(modm).
证明

必要性显然.为证明充分性,考虑使用反证法.如果 g 不是模 m 的原根,那么一定有 δm(g)<φ(m).由性质 2 和欧拉定理可知,δm(g)φ(m).由此,设 pφ(m)δm(g) 的一个素因子,就有 δm(g)φ(m)p.再次应用性质 2 就得到

gφ(m)p1(modm).

但是,p 也是 φ(m) 的一个因子,这就与题设条件矛盾.由此,原命题的充分性成立.

原根个数

原根如果存在,也未必唯一.一般地,对于模 m 既约剩余系中所有元素可能的阶和某个阶的元素数量,有如下结论:

定理

如果正整数 m 有原根 g,那么,当且仅当 dφ(m) 时,模 md 阶元素存在,且恰有 φ(d) 个.特别地,模 m 的原根个数为 φ(φ(m))

证明

根据原根的定义,所有模 m 的既约同余类都可以写作 gkmodm 的形式,且 k1,2,,φ(m) 之一.由性质 3,这些元素的阶等于

δm(gk)=φ(m)(φ(m),k).

因此,d 阶元素存在,当且仅当 dφ(m).而且,对于 dφ(m),令 d=φ(m)/d,这些元素的集合就是

A={gk:(φ(m),k)=d, 1kφ(m)}={gk:dk, (d,k/d)=1, 1k/dd}.

这些元素对应的 k=k/d 恰为那些不超过 d 且与 d 互素的正整数.由欧拉函数的定义,这就是 φ(d)

原根存在定理

本节将建立如下原根存在定理:

定理

m 的原根存在,当且仅当 m=1,2,4,pe,2pe,其中,p 是奇素数且 eN+

为说明这一结论,需要分别讨论如下四种情形:

  1. m=1,2,4,原根分别是 g=0,1,3,显然存在.

  2. m=pe 是奇素数的幂,其中,p 为奇素数,eN+

    引理 1

    对于奇素数 p,模 p 的原根存在.

    证明

    证明分为两步.

    第一步:对于 d(p1),同余方程 xd1(modp) 恰有 d 个互不相同的解.

    p1=kd,多项式

    f(x)=xd(k1)+xd(k2)++xd+1.

    根据 欧拉定理,同余方程 (xd1)f(x)=xp110(modp) 恰有 p1 个互不相同的解.这些解分别是 xd1f(x) 的零点.由 Lagrange 定理,它们分别至多只能有 d 个和 d(k1) 个互不相同的零点.由于 d+d(k1)=p1,前者只能恰好有 d 个互不相同的零点.这说明同余方程 xd1(modp) 恰有 d 个互不相同的解.

    第二步:对于 d(p1)d 阶元素恰好有 φ(d) 个.

    对于 φ(m) 的所有因子排序,然后应用归纳法.因为 1 阶元素只能是 1,只有一个,归纳起点成立.对于 d(p1),根据前文的性质 2,同余方程 xd1(modm) 的解一定满足 δp(x)d.因此,其中 d 阶元素个数为

    N(d)=ded, edN(e)=ded, edφ(e)=φ(d).

    第二个等号是归纳假设,第三个等号是欧拉函数的性质.由数学归纳法,就知道对于所有 d(p1),都恰有 φ(d)d 阶元素.

    特别地,对于 d=p1,恰有 φ(p1)(p1) 阶元素.因此,模 p 的原根存在.

    引理 2

    对于奇素数 peN+,模 pe 的原根存在.

    证明

    证明分为三步.

    第一步:存在模 p 的原根 g,使得 gp11(modp2)

    任取一个模 p 的原根 g.如果它不符合条件,即 gp11(modp2),那么,可以证明 g+p 符合条件:g+p 也是模 p 的原根,且

    (g+p)p1(p10)gp1+(p11)gp2p=gp1+gp2p(p1)1pgp21(modp2).

    第二步:上文选取的 g,对于任意 e1,都有 gφ(pe)1(modpe+1)

    g 的选取保证了 e=1 时,该式成立.假设该式对于 e 的情形成立,现要证明 e+1 的情形也成立.对于任意 e1,由欧拉定理可知,存在 λ 使得

    gφ(pe)=1+λpe

    成立.由归纳假设,λp.因为 φ(pe+1)=pφ(pe),所以

    gφ(pe+1)=(gφ(pe))p=(1+λpe)p1+λpe+1(modpe+2).

    结合 λp 可知,gφ(pe+1)1(modpe+2).由数学归纳法可知,命题成立.

    第三步:上文选取的 g,对于任意 e1,都是模 pe 的原根.

    g 的选取保证了 e=1 时,命题成立.假设命题对于 e 成立,现在要证明命题对于 e+1 也成立.将 δpe+1(g) 简记为 δ.由于 gδ1(modpe+1),必然也有 gδ1(modpe).由归纳假设可知,δpe(g)=φ(pe).因此,由前文阶的性质 2,就有 φ(pe)δ.又由欧拉定理可知,δφ(pe+1).但是,φ(pe+1)=pφ(pe).因此,只有两种可能:δ=φ(pe)δ=φ(pe+1).但是,第二步的结论说明,gφ(pe)1(modpe+1).因此,可能性 δ=φ(pe) 并不成立.唯一的可能性就是 δ=φ(pe+1).这就说明 gpe+1 的原根.由数学归纳法,命题对于所有 e1 都成立.

  3. m=2pe,其中,p 为奇素数,eN+

    引理 3

    对于奇素数 peN+,模 2pe 的原根存在.

    证明

    g 是模 pe 的原根,则 g+pe 也是模 pe 的原根.两者之间必然有一个是奇数,不妨设它就是 g.显然,(g,2pe)=1.设 δ=δ2pe(g),需要证明 δ=φ(2pe).由欧拉定理,δφ(2pe).同时,根据定义 gδ1(mod2pe),所以,gδ1(modpe),因此,由阶的性质 2 和 g 的选取可知,δpe(g)=φ(pe)δ.由欧拉函数表达式可知,φ(2pe)=φ(pe).所以,δ=δ2pe(g)=φ(pe).这就说明 δ 是模 2pe 的原根.

  4. m1,2,4,pe,2pe,其中,p 为奇素数,eN+

    引理 4

    假设 m1,2,4 且不存在奇素数 p 和正整数 e 使得 m=pem=2pe.那么,模 m 的原根不存在.

    证明

    对于 m=2ee3,假设模 m 的原根 g 存在.由于 gm,它一定是奇数.假设 g=2k+1kN,那么,有

    g2e2=(2k+1)2e21+(2e21)(2k)+(2e22)(2k)2=1+2e1k+2e1(2e21)k2=1+2e1(k+(2e21)k2)1(mod2e).

    倒数第二行中,因为 k(2e21)k2 奇偶性相同,所以它们的和是偶数.由阶的定义可知,δ2e(g)2e2<φ(2e)=2e1.这与假设中 g 是原根矛盾.由反证法,这样的原根并不存在.

    假设 m 满足所述条件,且不是 2 的幂,那么,一定存在 2<m1<m2m1m2 使得 m=m1m2 成立.假设模 m 的原根 g 存在.因为 gm,所以对于 i=1,2,都有 gmi.由欧拉定理可知,

    gφ(mi)1(modmi).

    由于 mi>2,所以 φ(mi) 为偶数,所以,对于 i=1,2,有

    g12φ(m1)φ(m2)1(modmi).

    中国剩余定理 可知

    g12φ(m1)φ(m2)1(modm).

    又因为 φ(m)=φ(m1)φ(m2),所以由阶的定义可知

    δm(g)12φ(m1)φ(m2)=12φ(m)<φ(m).

    这与 g 是模 m 的原根的假设矛盾.故而,由反证法知,模 m 的原根不存在.

综合以上四个引理,我们便给出了一个数存在原根的充要条件.

最小原根的范围估计

王元1和 Burgess2证明了素数 p 的最小原根 gp=O(p0.25+ϵ),其中 ϵ>0.Cohen, Odoni, and Stothers3和 Elliott and Murata4分别证明了该估计对于模数 p22p2 也成立,其中,p 是奇素数.由于对于 e>2,模 p2(或 2p2)的原根也是模 pe(或 2pe)的原根,所以,最小原根的上界 O(p0.25+ϵ) 对于所有情形都成立.

Fridlander5和 Salié6证明了素数 p 的最小原根 gp=Ω(logp)

这保证了暴力找一个数的最小原根时,复杂度可以接受.

Carmichael 函数

相对于模 m 元素的阶这一局部概念,Carmichael 函数是一个全局概念.它是所有与 m 互素的整数的幂次的最小公共循环节.

Carmichael 函数

对于 mN+,定义 λ(m) 为能够使得同余关系 an1(modm) 对于所有 am 都成立的最小正整数 n.函数 λ:N+N+ 就称为 Carmichael 函数

根据性质 2,能够使得 an1(modm) 对于所有 am 都成立,意味着 δm(a)n 对于所有 am 都成立.也就是说,符合这一条件的正整数 n,一定是全体 δm(a) 的公倍数.因此,最小的这样的 n 就是它们的最小公倍数:

λ(m)=lcm{δm(a):am}.

这也常用作 Carmichael 函数的等价定义.

反复应用性质 5 可知,一定存在某个元素 am 使得 δm(a)=λ(m).因此,上式也可以写作

λ(m)=max{δm(a):am}.

取得这一最值的元素 am 也称为模 mλ‑原根.它对于所有模数 m 都存在.

递推公式

Carmichael 函数是一个 数论函数.本节讨论它的一个递推公式,并由此给出原根存在定理的另一个证明.

虽然不是积性函数,但是计算 Carmichael 函数时,同样可以对互素的因子分别处理.

引理

对于互素的正整数 m1,m2,有 λ(m1m2)=[λ(m1),λ(m2)]

证明

a1a2 分别为模 m1 和模 m2λ‑原根.令 m=m1m2,由 中国剩余定理 可知,存在 am 使得 aai(modmi) 对于 i=1,2 都成立.由于 aλ(m)1(modm),所以对于 i=1,2,都有 aiλ(m)1(modmi),进而由性质 2 和 ai 的选取可知,λ(mi)=δmi(ai)λ(m).这就说明 [λ(m1),λ(m2)]λ(m)

反过来,对于任意 ami=1,2,都有 a[λ(m1),λ(m2)]1(modmi).应用中国剩余定理,就得到 a[λ(m1),λ(m2)]1(modm) 对于所有 am 都成立.根据 Carmichael 函数的定义可知,λ(m)[λ(m1),λ(m2)]

由此,命题中的等式成立.

因此,接下来只要计算 Carmichael 函数在素数幂处的取值.首先,处理 2 的幂次的情形.

引理

对于 m=2eeN+,有 λ(2)=1λ(4)=2,且对于 e3 都有 λ(m)=2e2

证明

对于 m=2,4 的情形,单独讨论即可.对于 m=2ee3 的情形,首先重复前文定理 4 的证明的第一部分,就得到 λ(m)2e2.进而,只需要证明存在 2e2 阶元素即可.为此,有

52e3=(1+22)2e3=1+22×2e3=1+2e11(mod2e).

这说明 δm(5)2e3,又因为 δm(5)2e2,所以,5 只能是 2e2 阶元素.这就说明,λ(m)=2e2

然后,处理奇素数幂的情形.

引理

对于 m=pe,其中,p 是奇素数且 eN+,有 λ(m)=pe1(p1)

证明

首先证明命题对于 e=1,即 m=p 是奇素数的情形成立.为此,由 Carmichael 函数的定义可知,与 p 互素的所有整数 a 都是同余方程 xλ(p)1(modp) 的解.在模 p 的意义下,该方程共有 p1 个互不相同的解.根据 Lagrange 定理 可知,p1λ(p).同时,欧拉定理要求,λ(p)φ(p)=p1.因此,λ(p)=p1

对于 m=pee>1 的情形,可以从证明 1+ppe1 阶元开始.为此,有

(1+p)pe11,(1+p)pe21+pe11(modpe).

所以,δm(1+p)=pe1.另外,设模 p 的原根为 g,那么,由于 gδm(g)1(modp),所以,由阶的性质 2 可知,p1δm(p).由 Carmichael 函数的定义和欧拉定理可知

pe1(p1)=[δm(p),pe1]λ(m)φ(m)=pe1(p1).

因此,λ(m)=pe1(p1)

将本节的结果简单归纳,就得到 Carmichael 函数的递推公式:

定理

对于任意正整数 m,有

λ(m)={φ(m),if m=1,2,4,pe for odd prime p and e1,12φ(m),if m=2e, e3,lcm{λ(p1e1),λ(p2e2),,λ(pses)},if m=p1e1p2e2pses for distinct p1,p2,,ps.

利用该递推公式可以加强前文的结果:

推论

对于正整数 m1,m2,有 λ([m1,m2])=[λ(m1),λ(m2)]

比较原根和 Carmichael 函数的定义可知,模 m 的原根存在,当且仅当 λ(m)=φ(m).从 Carmichael 函数的递推公式中,容易归纳出如下结果:

推论

m 的原根存在,当且仅当 m=1,2,4,pe,2pe,其中,p 是奇素数且 eN+

由于本节对于递推公式的证明并没有用到原根存在定理,因此,这就构成了对该定理的又一个证明.

Carmichael 数

利用 Carmichael 函数,可以讨论 Carmichael 数(卡迈克尔数,OEIS:A002997)的性质与分布.这是 Fermat 素性测试 一定无法正确排除的合数.

Carmichael 数

对于合数 n,如果对于所有整数 an 都有同余式 an11(modn) 成立,就称 nCarmichael 数

最小的 Carmichael 数是 561=3×11×17

由 Carmichael 函数的定义可知,合数 n 是 Carmichael 数当且仅当 λ(n)n1,其中 λ(n) 为 Carmichael 函数.进一步地,可以得到如下判断合数 n 是否为 Carmichael 数的方法:

Korselt 判别法7

合数 n 是 Carmichael 数当且仅当 n 无平方因子且对 n 的任意质因子 p 均有 (p1)(n1)

证明

首先证明条件的必要性.假设 λ(n)(n1).检查 Carmichael 函数的递推公式可知,如果 n 有平方因子 p,那么,一定有 pλ(n).但是 p(n1),矛盾.同理,Carmichael 函数的递推公式说明,(p1)λ(n),所以,也有 (p1)(n1)

然后证明条件的充分性.因为 n 是合数,所以它一定有奇素因子 p,因此 n1 是偶数,n 也就一定是奇数.对于无平方因子的奇合数 n,由 Carmichael 函数的递推公式可知,λ(n)=lcm{p1:pn}.因此,只要 (p1)(n1) 对于所有素因子 p 都成立,就一定有 λ(n)(n1)

从这一判别法出发,可以建立 Carmichael 数的一些简单性质:

推论

Carmichael 数是奇数,没有平方因子,而且至少有 3 个不同的素因子.

证明

前两条性质可以直接从 Korselt 判别法及其证明中得到.要得到第三条性质,只需要再证明:互异素数 p1,p2 的乘积 n=p1p2 一定不是 Carmichael 数.假设 n=p1p2 是 Carmichael 数.由 Korselt 判别法可知,(pi1)(n1).但是,有

n1=p1p21p21(modp11).

因此,(p11)(p21).同理,(p21)(p11).也就是说,p1=p2.这与假设矛盾.因此,Carmichael 数 n 至少有 3 个互异素因子.

利用解析数论还可以得到 Carmichael 数分布的一些性质.设 C(n) 为小于等于 n 的 Carmichael 数个数.Alford, Granville, and Pomerance8证明,对于充分大的 n,有 C(n)>n2/7.由此,Carmichael 数有无限多个.在这之前,Erdős9已经证明,C(n)<nexp(clnnlnlnlnnlnlnn),其中 c 为常数.因此,Carmichael 数的分布(相对于素数来说)十分稀疏.实际上,有10 C(109)=646C(1018)=1 401 644

参考资料与注释


  1. Wang Y. "On the least primitive root of a prime." (in Chinese). Acta Math Sinica, 1959, 4: 432–441; English transl. inSci. Sinica, 1961, 10: 1–14. 

  2. BURGESS, David A. "On character sums and primitive roots." Proceedings of the London Mathematical Society, 1962, 3.1: 179-192. 

  3. Cohen, S. D., R. W. K. Odoni, and W. W. Stothers. "On the least primitive root modulo p 2." Bulletin of the London Mathematical Society 6, no. 1 (1974): 42-46. 

  4. Elliott, P. D. T. A., and L. Murata. "The least primitive root mod 2p2." Mathematika 45, no. 2 (1998): 371-379. 

  5. FRIDLENDER, V. R. "On the least n-th power non-residue." Dokl. Akad. Nauk SSSR. 1949. p. 351-352. 

  6. SALIÉ, Hans. "Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl." Mathematische Nachrichten, 1949, 3.1: 7-8. 

  7. Korselt, A. R. (1899). "Problème chinois." L'Intermédiaire des Mathématiciens. 6: 142–143. 

  8. W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers." Annals of Mathematics. 140 (3): 703–722. 

  9. Erdős, P. (1956). "On pseudoprimes and Carmichael numbers." Publ. Math. Debrecen. 4 (3–4): 201–206. 

  10. PINCH, Richard GE. The Carmichael numbers up to 1020