betaFeedback

WorksMathematics

One more curious property of 17291729: The only Carmichael number of the form 2np3+12^np^3+1 with prime pp

Abstract

Florian Luca recently proved that if 2np3+12^np^3+1 is a Carmichael number for some prime pp and integer n≥1n\ge1, then p=3p=3. Here we complete the cubic classification by proving that 17291729, Hardy–Ramanujan taxicab number, is the only Carmichael number of the form 2np3+12^np^3+1 with pp prime and n≥1n\ge1. The proof identifies the unique possible multiplicatively dependent prime factor, sharpens the known bound on Fermat prime factors of 2nk+12^nk+1 from k2k^2 to 2k2k, derives the explicit bound n≤2742n\le2742, and concludes with a short sieve requiring neither factorisation nor primality testing.

Introduction

A Carmichael number is a composite integer NN such that aN≡a(modN)a^N \equiv a \pmod N for every integer aa. Korselt’s criterion [3] gives the following characterisation: a composite integer NN is Carmichael if and only if NN is square-free and q−1∣N−1q - 1 \mid N - 1 for every prime factor qq of NN. In particular, every Carmichael number is odd and has at least three distinct prime factors.

Cilleruelo, Luca and Pizarro-Madariaga [2] proved that for every fixed odd kk, the sequence (2nk+1)n≥1(2^n k+1)_{n\ge1} contains only finitely many Carmichael numbers, and that the smallest element of the set

K:={k odd:2nk+1 is Carmichael for some n≥1}\mathcal{K}:=\{k\text{ odd}:2^n k+1\text{ is Carmichael for some }n\ge1\}

is 27. In particular, for n=6n=6 and k=27k=27, we have 1729=2627+1=7⋅13⋅191729=2^6 27+1=7\cdot13\cdot19.

Alahmadi and Luca [1] subsequently proved that K\mathcal{K} contains no prime, and Luca and Randrianantenaina [6] proved that K\mathcal{K} contains no square of a prime. The cubic case is different, since 33=273^3=27 belongs to K\mathcal{K}.

Luca [5] addressed the prime part of the cubic case and proved the following result.

Theorem 1 (Luca [5]). If pp is prime and 2np3+12^n p^3+1 is Carmichael for some n≥1n\ge1, then p=3p=3.

Thus any Carmichael number of the form 2np3+12^n p^3+1 must occur in the sequence 2n33+1=27⋅2n+12^n3^3+1=27\cdot2^n+1.

Our main result completes the cubic classification.

Theorem 2. For n≥1n\ge1, 2n33+12^n3^3+1 is a Carmichael number if and only if n=6n=6. Consequently,

1729=2633+11729=2^6 3^3+1

is the unique Carmichael number in the sequence (2n33+1)n≥1(2^n3^3+1)_{n\ge1}.

Combining Theorem 1 and Theorem 2 gives the complete classification.

Corollary 1. For a prime pp and integer n≥1n\ge1, 2np3+12^n p^3+1 is Carmichael if and only if (p,n)=(3,6)(p,n)=(3,6).

In 2026, Luca [4] proved that, for every fixed odd m≥5m\ge5, there are only finitely many primes pp with pm∈Kp^m\in\mathcal{K}; the resulting bound on pp is ineffective. Tiebekabe [7] made several steps of [2, 4] explicit. In particular, if m≥3m\ge3 is odd, p>mp>m and 2npm+12^n p^m+1 is Carmichael, then n<25m4log⁡pn<25m^4\log p, and every prime factor qq of 2npm+12^n p^m+1 has q−1q-1 multiplicatively independent of 2npm2^n p^m [7 Theorems 1.1 and 1.3]. He also reported an exhaustive search showing that 1729 is the only Carmichael number 2npm+1≤10182^n p^m+1\le10^{18} with mm odd and 3≤m≤373\le m\le37 [7 Theorem 1.4].

Both structural results just quoted require p>mp>m, so they do not apply to the case p=m=3p=m=3 treated here. This exclusion is genuine: for 1729, the prime factor 13 satisfies 13−1=1213-1=12 and 1729−1=1231729-1=12^3, so a multiplicatively dependent prime factor occurs; see Lemma 1. Moreover, the restriction 27⋅2n+1≤101827\cdot2^n+1\le10^{18} covers only n≤55n\le55, whereas Theorem 2 covers all n≥1n\ge1.

printed: 2020 Mathematics Subject Classification. 11A05, 11A51, 11A67. The organization of this paper is as follows. In § 2, we define and classify the dependent and independent prime factors of NnN_n. § 3 presents a sharper version of the bound in [2 Lemma 2] for Fermat prime factors. In § 4, we first bound the largest exponent nn that can yield a Carmichael number NnN_n, and then we give explicit bounds for the size of prime factors of NnN_n. § 5 has the sieve for the divisors of NnN_n and this is where we also present the proofs of Theorem 2 and Corollary 1. Finally, we include an outlook section where we discuss possible future directions.

Prime Factors and Dependency

Let Nn:=2n33+1=27 2n+1N_n := 2^n3^3 + 1 = 27\,2^n + 1. Assume from now on, unless stated otherwise, that NnN_n is Carmichael. If q∣Nnq \mid N_n is prime, Korselt’s criterion gives q−1∣Nn−1=2n33q - 1 \mid N_n - 1 = 2^n3^3. Therefore every prime factor of NnN_n has the form

q=2a3b+1,1≤a≤n,0≤b≤3.(1)q = 2^a3^b + 1, \qquad1 \le a \le n,\qquad0 \le b \le3. \tag*{(1)}

We call the integers q−1q - 1 and Nn−1N_n - 1 multiplicatively dependent, if there exist positive integers u,vu,v such that

(2a3b)u=(2n33)v.(2)(2^a3^b)^u = (2^n3^3)^v. \tag*{(2)}

For b=0b = 0 we have q=2a+1q = 2^a + 1, so aa must be a power of 2 and qq is a Fermat prime. For b≥1b \ge1, we now determine when q−1=2a3bq - 1 = 2^a3^b and Nn−1=2n33N_n - 1 = 2^n3^3 can be multiplicatively dependent. In the analogous cubic problem with p>3p > 3, Luca excludes this possibility [5 Section 2.1]; for p=3p = 3 it does occur, as the factor 13 of 1729 shows.

Here, we recite a known result for our cases [2 Lemma 3].

Lemma 1. Let q=2a3b+1∣Nnq = 2^a3^b + 1 \mid N_n be prime, with 1≤b≤31 \le b \le3. If Nn−1N_n - 1 and q−1q - 1 are multiplicatively dependent, then 3∣n3 \mid n, b=1b = 1 and a=n/3a = n/3. Thus the only possible dependent prime factor is

Dn:=3 2n/3+1.(3)D_n := 3\,2^{n/3} + 1. \tag*{(3)}

Conversely, if 3∣n3 \mid n, then Dn∣NnD_n \mid N_n; if DnD_n is prime, it is the unique dependent prime factor of NnN_n.

Proof. If q−1q - 1 and Nn−1N_n - 1 are multiplicatively dependent, comparing the 2-adic and 3-adic valuations in (2) gives au=nvau = nv and bu=3vbu = 3v, hence

3a=nb.(4)3a = nb. \tag*{(4)}

Conversely, (4) gives (2a3b)3=(2n33)b(2^a3^b)^3 = (2^n3^3)^b, so it is equivalent to multiplicative dependence in the present setting.

If b=3b = 3, then (4) gives a=na = n and q=Nnq = N_n. This is a contradiction since qq is prime whereas NnN_n is Carmichael and therefore composite.

If b=2b = 2, then 3a=2n3a = 2n, so n=3tn = 3t and a=2ta = 2t for some t≥1t \ge1. Put x:=3 2tx := 3\,2^t. Then q=x2+1q = x^2 + 1 and Nn=x3+1N_n = x^3 + 1. Since q∣Nnq \mid N_n and x2≡−1(modq)x^2 \equiv-1 \pmod q, we have x3+1≡−x+1(modq)x^3 + 1 \equiv-x + 1 \pmod q. Thus q∣x−1q \mid x - 1, impossible because 0<x−1<x2+1=q0 < x - 1 < x^2 + 1 = q.

Finally, if b=1b = 1, then (4) gives n=3an = 3a. If n=3tn = 3t and x:=3 2tx := 3\,2^t, then

Nn=x3+1=(x+1)(x2−x+1),N_n = x^3 + 1 = (x + 1)(x^2 - x + 1),

so Dn=x+1=3 2t+1D_n = x + 1 = 3\,2^t + 1 divides NnN_n. If DnD_n is prime, then Dn−1=3 2tD_n - 1 = 3\,2^t and Nn−1=(3 2t)3=(Dn−1)3N_n - 1 = (3\,2^t)^3 = (D_n - 1)^3, proving dependence. Uniqueness follows because DnD_n is completely determined by nn. □

Note that b=0b = 0 possibility for the prime divisors of NnN_n is ignored in Lemma 1. This is because b=0b = 0 forces v=0v = 0, and later au=0au = 0. This does not fit into the multiplicative dependence definition with positive uu and vv. We handle b=0b = 0 case next.

Eliminating Fermat Prime Factors

By [2 Lemma 2], every Fermat prime factor qq of 2nk+12^n k + 1 is less than k2k^2. For k=27k = 27 this gives the preliminary bound q<729q < 729. The following elementary theorem sharpens k2k^2 to 2k2k, and yields q<54q < 54 in the present case.

Theorem 3. Let k≥3k \ge3 be odd, n≥0n \ge0, and let q=22n+1q = 2^{2^n} + 1 be a prime dividing 2nk+12^n k + 1. Then q<2kq < 2k.

Proof. If α=0\alpha=0, then q=3<6≤2kq=3<6\le2k. Assume α≥1\alpha\ge1, put c:=2αc:=2^\alpha, so that 2c≡−1(modq)2^c\equiv-1\pmod q, and write n=ct+rn=ct+r with 0≤r<c0\le r<c. From q∣2nk+1q\mid2^nk+1 we obtain 0≡(−1)t2rk+1(modq)0\equiv(-1)^t2^{rk}+1\pmod q. Multiplying by 2c−r2^{c-r} and using 2c≡−1(modq)2^c\equiv-1\pmod q gives

k≡(−1)t2c−r(modq).(5)k\equiv(-1)^t2^{c-r}\pmod q. \tag*{(5)}

Assume, for a contradiction, that q≥2kq\ge2k. Then 0<k<q0<k<q and 2≤2c−r≤2c<q2\le2^{c-r}\le2^c<q. If tt is even, (5) forces k≥3k\ge3 to be even and yields a contradiction. If tt is odd, (5) forces k=q−2c−rk=q-2^{c-r}. If r=0r=0, then k=q−2c=1k=q-2^c=1, a contradiction. If r≥1r\ge1, then 2c−r≤2c−1=(q−1)/22^{c-r}\le2^{c-1}=(q-1)/2, so k≥(q+1)/2>q/2k\ge(q+1)/2>q/2, contradicting q≥2kq\ge2k.

Thus, for k=27k=27, the only possible Fermat prime factors of NnN_n are 3, 5 and 17.

Theorem 3 has several useful consequences. First off, the bound q<2kq<2k is attained up to one unit for every Fermat prime q≥5q\ge5. Indeed, let q=2c+1q=2^c+1 be a Fermat prime with c≥2c\ge2, and set k=(q+1)/2=2c−1+1k=(q+1)/2=2^{c-1}+1 and n:=c+1n:=c+1. Then kk is odd and

2nk+1=2c+1(2c−1+1)+1=(2c+1)2=q2.2^nk+1=2^{c+1}(2^{c-1}+1)+1=(2^c+1)^2=q^2.

Thus q∣2nk+1q\mid2^nk+1 and q=2k−1q=2k-1.

Moreover, the theorem also improves the bound for the entire Fermat part. Let Fj:=22j+1F_j:=2^{2^j}+1 be the Fermat numbers, and suppose that FjF_j is the largest Fermat prime dividing 2nk+12^nk+1. Since F0F1⋅⋅⋅Fj−1=Fj−2F_0F_1\mathinner{\cdotp\cdotp\cdotp}F_{j-1}=F_j-2, we have F0F1⋅⋅⋅Fj=(Fj−1)2−1<(Fj−1)2F_0F_1\mathinner{\cdotp\cdotp\cdotp}F_j=(F_j-1)^2-1<(F_j-1)^2. Therefore, the product FF of the distinct Fermat prime divisors of 2nk+12^nk+1 satisfies

F<4k2.F<4k^2.

For comparison, [2 (15)] obtains F<k4F<k^4 from the earlier individual bound Fj<k2F_j<k^2. In Luca’s cubic setting k=p3k=p^3, this appears as F<p12=k4F<p^{12}=k^4; see [5 Section 2.1]. Thus Theorem 3 improves the corresponding general Fermat part estimate from k4k^4 to 4k24k^2.

To exemplify this, we look at our case k=27k=27. The earlier bound q<729q<729 leaves 257 as an additional possible Fermat prime factor that must be excluded separately. Indeed, 27−1≡−19(mod257)27^{-1}\equiv-19\pmod{257}, so 257∣27n+1257\mid27^n+1 would imply 2n≡19(mod257)2^n\equiv19\pmod{257}, but ord⁡257(2)=16\operatorname{ord}_{257}(2)=16, where ord⁡r(s)\operatorname{ord}_r(s) is the smallest positive integer uu such that su≡1(modr)s^u\equiv1\pmod r. A direct check of the j=1,2,…,16j=1,2,\ldots,16 powers 2j2^j modulo 257 shows that 19∉⟨2⟩25719\notin\langle2\rangle_{257}, where ⟨2⟩257\langle2\rangle_{257} denotes the orbit of powers of 2 modulo 257. Hence 257∤Nn257\nmid N_n. The sharper bound q<54q<54 makes this additional check unnecessary.

Now we further investigate some properties of NnN_n.

Lemma 2. Let Nn=27⋅2n+1N_n=27\cdot2^n+1. Then

i. 3∤Nn3\nmid N_n;

ii. 5∣Nn5\mid N_n if and only if n≡1(mod4)n\equiv1\pmod4; and

iii. 17∤Nn17\nmid N_n.

Proof. i. Obvious since 3∣273\mid27.

ii. We have 5∣Nn5\mid N_n if and only if 2n+1≡−1≡22(mod5)2^{n+1}\equiv-1\equiv2^2\pmod5, since 27≡2(mod5)27\equiv2\pmod5. As ord⁡5(2)=4\operatorname{ord}_5(2)=4, this is equivalent to n≡1(mod4)n\equiv1\pmod4.

iii. Since 27≡10(mod17)27\equiv10\pmod{17} and 10−1≡12≡−5(mod17)10^{-1}\equiv12\equiv-5\pmod{17}, we have 17∣Nn17\mid N_n if and only if 2n≡5(mod17)2^n\equiv5\pmod{17}. However, ord⁡17(2)=8\operatorname{ord}_{17}(2)=8 and the orbit of powers of 2 modulo 17 is ⟨2⟩17=(1 2 4 8 16 15 13 9)\langle2\rangle_{17}=(1\ 2\ 4\ 8\ 16\ 15\ 13\ 9) (mod 17), which does not contain 5.

Theorem 4. If NnN_n is Carmichael, then NnN_n has no Fermat prime factor. In particular, every prime divisor of NnN_n has b≥1b\ge1 in (1), and n≢1(mod4)n\not\equiv1\pmod4.

Proof. By Theorem 3 and Lemma 2, the only Fermat prime that can divide NnN_n is 5. Indeed, 3∤Nn3\nmid N_n and 17∤Nn17\nmid N_n. Suppose that 5∣Nn5\mid N_n. Since NnN_n is square-free, 5 occurs exactly once in its prime factorisation. Therefore every other prime divisor qq of NnN_n is not a Fermat prime and, by (1), has the form q=23b+1q=2^3b+1 with b≥1b\ge1, implying q≡1(mod3)q\equiv1\pmod3. Reducing the prime factorisation of NnN_n modulo 3 therefore gives Nn≡5≡2(mod3)N_n\equiv5\equiv2\pmod3, contradicting Nn≡1(mod3)N_n\equiv1\pmod3. Hence, NnN_n has no Fermat prime factor. The final assertion follows from part (ii) of Lemma 2.

Bounding nn

Here we mostly follow the footsteps of [2] to find a sharper bound for nn of NnN_n and the exponents of 22 that appear in the representation of the prime divisors of NnN_n. This enables us to limit the number of cases to consider for a proof of Theorem 2.

Let RR denote the product of all prime factors q=2a3b+1q=2^{a}3^{b}+1 of NnN_n such that q−1q-1 and Nn−1N_n-1 are multiplicatively independent. By Theorem 4, all these factors have b≥1b\geq1. By Lemma 1, at most one prime factor, namely DnD_n, is omitted from RR, and this can happen only when 3∣n3\mid n. Hence,

R=Nnif 3∤n,andR≥NnDnif 3∣n.(6)R=N_n\quad\text{if }3\nmid n,\qquad\text{and}\qquad R\geq\frac{N_n}{D_n}\quad\text{if }3\mid n. \tag*{(6)}

Lemma 3. Let q=2a3b+1q=2^{a}3^{b}+1, with b∈{1,2,3}b\in\{1,2,3\}, be an multiplicatively independent prime factor of NnN_n. Then

2λ≡ε(modq),(λ,ε)={(n−3a,1),b=1,(2n−3a,−1),b=2,(n−a,1),b=3.(7)2^{\lambda}\equiv\varepsilon\pmod q,\qquad (\lambda,\varepsilon)= \begin{cases} (n-3a,1), & b=1,\\ (2n-3a,-1), & b=2,\\ (n-a,1), & b=3. \end{cases} \tag*{(7)}

Moreover, 0<∣λ∣≤2n0<|\lambda|\leq2n.

Proof. The relations q=2a3b+1q=2^{a}3^{b}+1 and Nn=2n33+1N_n=2^{n}3^{3}+1, together with q∣Nnq\mid N_n, give 2a3b≡−1(modq)2^{a}3^{b}\equiv-1\pmod q and 2n33≡−1(modq)2^{n}3^{3}\equiv-1\pmod q. Since NnN_n is odd and Nn≡1(mod3)N_n\equiv1\pmod3, no prime divisor qq of NnN_n can be 2 or 3. Thus gcd⁡(q,6)=1\gcd(q,6)=1, so both 2 and 3 are invertible modulo qq.

If b=1b=1, cubing the first congruence and substituting into the second gives 2n−3a≡1(modq)2^{n-3a}\equiv1\pmod q. If b=2b=2, cubing the first congruence and squaring the second gives 22n−3a≡−1(modq)2^{2n-3a}\equiv-1\pmod q. If b=3b=3, direct substitution gives 2n−a≡1(modq)2^{n-a}\equiv1\pmod q. These are exactly the three cases in (7).

Regardless of the choice of bb, if λ=0\lambda=0, then (7) shows that 3a=nb3a=nb, which shows that these terms are multiplicatively dependent (4). Hence, λ≠0\lambda\neq0. Since 1≤a≤n1\leq a\leq n, the three cases also give ∣λ∣≤2n|\lambda|\leq2n.

Squaring (7) gives 22λ≡1(modq)2^{2\lambda}\equiv1\pmod q, and implies

ord⁡q(2)∣2∣λ∣,ord⁡q(2)≤2∣λ∣≤4n.(8)\operatorname{ord}_{q}(2)\mid2|\lambda|,\qquad\operatorname{ord}_{q}(2)\leq2|\lambda|\leq4n. \tag*{(8)}

On the other hand, we have ord⁡q(2)∣q−1\operatorname{ord}_{q}(2)\mid q-1, while Korselt’s criterion implies q−1∣2n33q-1\mid2^{n}3^{3}. Putting together, we see that

ord⁡q(2)=2γ3s,0≤γ≤n and s∈{0,1,2,3}.(9)\operatorname{ord}_{q}(2)=2^{\gamma}3^{s},\qquad0\leq\gamma\leq n\text{ and }s\in\{0,1,2,3\}. \tag*{(9)}

With these relations at hand, we derive a general bound for divisors M∣2nk+1M\mid2^{n}k+1, with k≥3k\geq3 odd, satisfying 2u≡1(modM)2^{u}\equiv1\pmod M for some small uu. The argument refines the box-principle method of [2 Lemma 4], also used in [5 Section 2.1].

Lemma 4. Let k≥3k\geq3 be odd, put L:=log⁡2kL:=\log_{2}k, let MM be a positive divisor of 2nk+12^{n}k+1, and let u≥1u\geq1 satisfy 2u≡1(modM)2^{u}\equiv1\pmod M. Put B:=⌊u/L⌋B:=\lfloor\sqrt{u/L}\rfloor and A:=⌊u/(B+1)⌋A:=\lfloor u/(B+1)\rfloor. Then

A+BL<2uL,M≤2AkB+1.(10)A+BL<2\sqrt{uL},\qquad M\leq2^{Ak^{B}}+1. \tag*{(10)}

In particular, M<22uL+1M<2^{2\sqrt{uL}}+1.

Proof. If M=1M=1, there is nothing to prove, so assume M>1M>1. Since B+1>u/LB+1>\sqrt{u/L}, we have A≤u/(B+1)<uLA\leq u/(B+1)<\sqrt{uL}; also B≤u/LB\leq\sqrt{u/L} gives BL≤uLBL\leq\sqrt{uL}. Hence, A+BL<2uLA+BL<2\sqrt{uL}. Moreover, A+1>u/(B+1)A+1>u/(B+1), so (A+1)(B+1)>u(A+1)(B+1)>u.

Since M∣2nk+1M\mid2^{n}k+1, we have gcd⁡(M,2k)=1\gcd(M,2k)=1 and k≡−2−n(modM)k\equiv-2^{-n}\pmod M. Thus, for (α,β)∈{0,…,A}×{0,…,B}(\alpha,\beta)\in\{0,\ldots,A\}\times\{0,\ldots,B\},

2αkβ≡(−1)β2α−nβ(modM).2^{\alpha}k^{\beta}\equiv(-1)^{\beta}2^{\alpha-n\beta}\pmod M.

There are (A+1)(B+1)>u(A+1)(B+1)>u such pairs but only uu residue classes modulo uu. Hence, by the pigeonhole principle, there exist two distinct pairs (α1,β1)(\alpha_{1},\beta_{1}) and (α2,β2)(\alpha_{2},\beta_{2}) that satisfy α1−nβ1≡α2−nβ2(modu)\alpha_{1}-n\beta_{1}\equiv\alpha_{2}-n\beta_{2}\pmod u. Since 2u≡1(modM)2^{u}\equiv1\pmod M, it follows that (−1)β12α1kβ1≡(−1)β22α2kβ2(modM)(-1)^{\beta_{1}}2^{\alpha_{1}}k^{\beta_{1}}\equiv(-1)^{\beta_{2}}2^{\alpha_{2}}k^{\beta_{2}}\pmod M.

After cancelling the common powers of 2 and kk, which are invertible modulo MM, we obtain M∣WM\mid W, where

W:=2x1ky1−δ2x2ky2,δ:=(−1)β1+β2∈{±1},W:=2^{x_{1}}k^{y_{1}}-\delta2^{x_{2}}k^{y_{2}},\qquad\delta:=(-1)^{\beta_{1}+\beta_{2}}\in\{\pm1\},

with 0≤xi≤A0\leq x_i\leq A, 0≤yi≤B0\leq y_i\leq B, min⁡(x1,x2)=0\min(x_1,x_2)=0 and min⁡(y1,y2)=0\min(y_1,y_2)=0.

We have W≠0W\neq0. Indeed, this is immediate if δ=−1\delta=-1. If δ=1\delta=1 and W=0W=0, then 2x1ky1=2x2ky22^{x_1}k^{y_1}=2^{x_2}k^{y_2}; since gcd⁡(2,k)=1\gcd(2,k)=1 and k≥3k\geq3, this forces x1=x2x_1=x_2 and y1=y2y_1=y_2, contradicting the choice of distinct pairs. While bounding ∣W∣|W|, we encounter two cases up to switching the order of the pairs (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2). If x1=y1=0x_1=y_1=0, then ∣W∣≤1+2AkB|W|\le1+2^{A}k^{B}. Otherwise, we may assume x1=0x_1=0 and y2=0y_2=0, and then ∣W∣≤kB+2A≤1+2AkB|W|\le k^{B}+2^{A}\le1+2^{A}k^{B}, since (2A−1)(kB−1)≥0(2^{A}-1)(k^{B}-1)\ge0. Thus 0<∣W∣≤1+2AkB0<|W|\le1+2^{A}k^{B}. Since M∣WM\mid W, we obtain M≤2AkB+1M\le2^{A}k^{B}+1, and (10) gives M<22uL+1M<2^{2\sqrt{uL}}+1.

For k=27=33k=27=3^3, the following is immediate.

Corollary 2. If q=2a3b+1q=2^a3^b+1 is an independent prime factor of the Carmichael number Nn=27 2n+1N_n=27\,2^n+1, then

a+blog⁡23<4nlog⁡227.a+b\log_2 3<4\sqrt{n\log_2 27}.

In particular, a<4nlog⁡227a<4\sqrt{n\log_2 27}.

Proof. Apply Lemma 4 with k=27k=27, M=qM=q and u=ord⁡q(2)u=\operatorname{ord}_q(2). Since (8) gives u≤4nu\le4n, we have q−1≤2A27B<22ulog⁡227≤24nlog⁡227q-1\le2^{A}27^{B}<2^{2\sqrt{u\log_2 27}}\le2^{4\sqrt{n\log_2 27}}. Taking base 2 logarithms yields the stated inequality.

We now bound the product RR of all independent prime factors of NnN_n.

Lemma 5. For each s∈{0,1,2,3}s\in\{0,1,2,3\} with 3s≤4n3^s\le4n, let usu_s be the largest integer of the form 2γ3s2^\gamma3^s not exceeding 4n4n, and set

Gs:=gcd⁡(2us−1,Nn).(11)G_s:=\gcd(2^{u_s}-1,N_n). \tag*{(11)}

If 3s>4n3^s>4n, set Gs:=1G_s:=1. Then every independent prime factor of NnN_n divides at least one of G0,G1,G2,G3G_0,G_1,G_2,G_3, and

R≤∏s=03Gs,R<216nlog⁡227+4.(12)R\le\prod_{s=0}^{3}G_s,\qquad R<2^{16\sqrt{n\log_2 27}+4}. \tag*{(12)}

Proof. Let qq be an independent prime factor of NnN_n. By (9), ord⁡q(2)=2γ3s\operatorname{ord}_q(2)=2^\gamma3^s for some 0≤γ≤n0\le\gamma\le n and s∈{0,1,2,3}s\in\{0,1,2,3\}, and (8) gives ord⁡q(2)≤4n\operatorname{ord}_q(2)\le4n. Hence, 3s≤4n3^s\le4n, so usu_s is defined. By maximality of the exponent of 2 in usu_s, we have ord⁡q(2)∣us\operatorname{ord}_q(2)\mid u_s. Therefore q∣2us−1q\mid2^{u_s}-1, and since q∣Nnq\mid N_n, we obtain q∣Gsq\mid G_s.

Thus every prime factor of RR divides at least one GsG_s. Since RR is squarefree, R∣∏s=03GsR\mid\prod_{s=0}^{3}G_s, proving the first inequality in (12). For every $G_s>1, {xref}Lemma 4 with $M=G_s$, $k=27$ and $u=u_s\le 4n$ gives $G_s<2^{4\sqrt{n\log_2 27}}+1<2^{4\sqrt{n\log_2 27}+1}$. There are at most four such factors, which gives the second inequality in {xref}(12)`.

Proposition 1. If Nn=27 2n+1N_n=27\,2^n+1 is Carmichael, then n≤2742n\le2742. If, in addition, 3∤n3\nmid n, then n<1215n<1215.

Proof. Let y:=ny:=\sqrt{n} and c:=16log⁡227c:=16\sqrt{\log_2 27}.

If 3∤n3\nmid n, then (6) and Lemma 5 give Nn−1=27 2y2<Nn=R<2cy+4N_n-1=27\,2^{y^2}<N_n=R<2^{cy+4}. Taking logarithms to base 2 gives y2−cy+log⁡227−4<0y^2-cy+\log_2 27-4<0. The larger root of the corresponding quadratic is approximately 34.867534.8675. The inequality and the larger root imply n=y2<1215.741n=y^2<1215.741. Hence, n≤1215n\le1215; since 3∤n3\nmid n, the value 1215 is excluded and therefore n<1215n<1215.

If 3∣n3\mid n, then (6) gives R≥Nn/DnR\ge N_n/D_n. Put x:=Nn−13=3 2n/3x:=\sqrt[3]{N_n-1}=3\,2^{n/3}. Since Nn=x3+1=(x+1)(x2−x+1)N_n=x^3+1=(x+1)(x^2-x+1) and Dn=x+1D_n=x+1, we have R≥x2−x+1>x2/2=9 22n/3−1R\ge x^2-x+1>x^2/2=9\,2^{2n/3-1}. Combining this with Lemma 5 gives

9 22y2/3−1<2cy+4.9\,2^{2y^2/3-1}<2^{cy+4}.

Taking logarithms to base 2 yields (2/3)y2−cy+log⁡29−5<0(2/3)y^2-cy+\log_2 9-5<0. Similarly, the larger root is approximately 52.386152.3861, and we get n=y2<2744.303n=y^2<2744.303. Since 3∣n3\mid n, it follows that n≤2742n\le2742.

Since nn is now bounded, Corollary 2 gives an explicit bound on the exponent aa of every independent prime factor. If 3∤n3\nmid n, then n<1215n<1215, hence a<41215log⁡227<304.04a<4\sqrt{1215\log_2 27}<304.04, so a≤303a\le303. If 3∣n3\mid n, then n≤2742n\le2742, hence a<42742log⁡227<456.74a<4\sqrt{2742\log_2 27}<456.74, so a≤456a\le456. In the latter case, there may also be the unique dependent prime factor Dn=3 2n/3+1D_n=3\,2^{n/3}+1. Notice that any multiplicatively dependent term candidate DnD_n is known explicitly and also bounded since nn is bounded.

Comparison with Earlier Bounds

Here we would like to highlight how the progress on the bounds evolved. The general bound of [2 Theorem 1],

n<22⋅107τ(k)2(log⁡k)2ω(k),n<2^{2\cdot10^7\tau(k)^2(\log k)^2\omega(k)},

is effective but very large in the present case. For k=27k=27, where τ(27)=4\tau(27)=4 and ω(27)=1\omega(27)=1, it gives n<221016(log⁡27)2<23.48×109n<2^{2^{10^{16}(\log27)^2}}<2^{3.48\times10^9}.

A much smaller bound can be extracted from the box principle argument of [5 Section 2.1], which adapts [2 Lemma 4]. After separating the possible dependent factor, the estimate for the independent part applies equally to p=3p=3. For n≥7n\ge7 the argument gives, for each of the four order classes,

Gs≤26nlog⁡33nlog⁡3+1<210.5nlog⁡3,G_s\le2^{6\sqrt{n\log3}}3^{\sqrt{n\log3}}+1<2^{10.5\sqrt{n\log3}},

and hence R<242nlog⁡3R<2^{42\sqrt{n\log3}}. If there is no dependent factor, then R=NnR=N_n, so n+log⁡227<42nlog⁡3n+\log_2 27<42\sqrt{n\log3}, which gives n≤1928n\le1928.

If a dependent factor occurs, then 3∣n3\mid n and Dn=3 2n/3+1≤(7/2)2n/3D_n=3\,2^{n/3}+1\le(7/2)2^{n/3}. In this case Nn=DnRN_n=D_nR, so 2n3+log⁡2(54/7)<42nlog⁡3\frac{2n}{3}+\log_2(54/7)<42\sqrt{n\log3}, which gives n≤4351n\le4351 and hence, since 3∣n3\mid n, n≤4350n\le4350. The values n≤6n\le6 are already contained in this range.

Similar arguments can lead to a fixed bound for the exponent of an independent prime factor. By [2 Lemma 4], if q=2ad+1q=2^ad+1 divides a Carmichael number 2nk+12^{nk}+1, with d∣kd\mid k, d>1d>1, and 2ad2^{ad} multiplicatively independent of 2nk2^{nk}, then a<7nlog⁡ka<7\sqrt{n\log k} whenever n>3log⁡kn>3\log k. For k=27k=27 and n≤4350n\le4350, this gives a<74350log⁡27<838.16a<7\sqrt{4350\log27}<838.16, hence a≤838a\le838. If n≤3log⁡27n\le3\log27, then n≤9n\le9 and trivially a≤n≤9a\le n\le9. Thus a≤838a\le838 covers all independent prime factors in the range n≤4350n\le4350.

Lemma 4 may be viewed as the same box principle argument with the two sides of the box chosen asymmetrically and optimised with respect to the relative sizes of 22 and kk. For k=27k=27, since log⁡227=3log⁡3/log⁡2\log_2 27=3\log3/\log2, we have 4nlog⁡227<8.33nlog⁡34\sqrt{n}\log_2 27<8.33\sqrt{n\log3}. Thus the new argument gives Gs<28.33nlog⁡3+1G_s<2^{8.33\sqrt{n\log3}}+1, improving the estimate on GsG_s above. Likewise, Corollary 2 gives a<4nlog⁡227<4.81nlog⁡27a<4\sqrt{n}\log_2 27<4.81\sqrt{n\log27} instead of a<7nlog⁡27a<7\sqrt{n\log27}. Together with the treatment of the dependent factor, these improvements reduce the global range to n≤2742n\le2742 and give a≤456a\le456 for every independent prime factor.

For comparison, the explicit estimate n<25m4log⁡pn<25m^4\log p in [7 Theorem 1.1(ii)] is obtained under the hypothesis p>mp>m. It therefore does not cover the exceptional cubic case considered here, where p=m=3p=m=3.

A Factorisation Free Sieve

For each admissible nn, define amax⁡(n):=min⁡{n,⌊4nlog⁡227⌋−1}a_{\max}(n):=\min\{n,\lfloor4\sqrt{n}\log_2 27\rfloor-1\} and

Cn:={2a3b+1:1≤a≤amax⁡(n), 1≤b≤3,2a3b+1<Nn, 2a3b+1∣Nn}.C_n:=\left\{2^a3^b+1: \begin{array}{l} 1\le a\le a_{\max}(n),\ 1\le b\le3,\\ 2^a3^b+1<N_n,\ 2^a3^b+1\mid N_n \end{array} \right\}.

If 3∣n3\mid n, we additionally include Dn=3 2n/3+1D_n=3\,2^{n/3}+1 in CnC_n.

Proposition 2. If NnN_n is Carmichael, then every prime divisor of NnN_n belongs to CnC_n. Furthermore, if Pn:=∏d∈CndP_n:=\prod_{d\in C_n}d, then Nn∣PnN_n\mid P_n.

Proof. Let q∣Nnq\mid N_n be prime. By (1) and Theorem 4, q=2a3b+1q=2^a3^b+1 with 1≤b≤31\le b\le3.

Suppose first that q−1q-1 and Nn−1N_n-1 are multiplicatively independent. By Corollary 2, a<4nlog⁡227a<4\sqrt{n}\log_2 27; since aa is an integer, a≤⌊4nlog⁡227⌋−1a\le\lfloor4\sqrt{n}\log_2 27\rfloor-1. As also a≤na\le n, we have a≤amax⁡(n)a\le a_{\max}(n). Finally, q∣Nnq\mid N_n and q<Nnq<N_n because NnN_n is composite, so q∈Cnq\in C_n.

If q−1q-1 and Nn−1N_n-1 are dependent, then Lemma 1 gives 3∣n3\mid n and q=Dnq=D_n, which is included in CnC_n. Thus every prime divisor of NnN_n belongs to CnC_n.

Since NnN_n is Carmichael, it is square-free. Hence, NnN_n is the product of its distinct prime divisors. Every such prime belongs to CnC_n and therefore divides PnP_n, so Nn∣PnN_n\mid P_n. □

Proof of Theorem 2. Proposition 2 gives a finite sieve requiring neither factorisation of NnN_n nor primality tests for the elements of CnC_n: any admissible nn for which Nn∤PnN_n\nmid P_n cannot yield a Carmichael number. By Proposition 1, it suffices to consider 1≤n<12151\le n<1215 with 3∤n3\nmid n, and 1≤n≤27421\le n\le2742 with 3∣n3\mid n. For each such nn we computed Pn mod NnP_n\bmod N_n with exact integer arithmetic. The only surviving value is

n=6,n=6,

for which

C6={7,13,19},N6=276+1=7⋅13⋅19=1729.C_6=\{7,13,19\},\qquad N_6=27^6+1=7\cdot13\cdot19=1729.

As verified above by Korselt’s criterion, 1729 is Carmichael. This completes the proof. □

As an independent consistency check, we also ran the sieve with the earlier bounds of § 4, over 1≤n≤43501 \le n \le4350 with 1≤a≤n1 \le a \le n and with DnD_n included whenever 3∣n3 \mid n. Again, the only surviving value is n=6n = 6. The sharper bounds of Proposition 1 therefore reduce the computational search substantially without changing the final conclusion.

Finally, we prove Corollary 1.

Proof of Corollary 1. If 2np3+12^n p^3 + 1 is Carmichael, then Theorem 1 gives p=3p = 3 and Theorem 2 gives n=6n = 6. Conversely, 1729=7⋅13⋅191729 = 7 \cdot13 \cdot19 is square-free and 66, 1212 and 1818 all divide 17281728, so 17291729 is Carmichael by Korselt’s criterion. □

Outlook

In [5], Luca studies primes p>3p > 3. In § 2, He describes how p=3p = 3 leads to the emergence of multiplicatively dependent factors. However, it is known that there would be at most one dependent prime factor [2].

In the taxicab number 1729=7⋅13⋅191729 = 7 \cdot13 \cdot19, the factor 13=D6=3⋅22+113 = D_6 = 3 \cdot2^2 + 1 is precisely the dependent prime factor (of Lemma 1 since 1728=1231728 = 12^3), while 7=2⋅3+17 = 2 \cdot3 + 1 and 19=2⋅32+119 = 2 \cdot3^2 + 1 are independent. We observe that the exact x3+1x^3 + 1 structure that we see in § 2 occurs in another similar Carmichael number 46657=26⋅36+1=363+1=13⋅37⋅9746657 = 2^6 \cdot3^6 + 1 = 36^3 + 1 = 13 \cdot37 \cdot97. This was also noticed in [7]. Here 37=36+137 = 3^6 + 1 is the unique dependent factor. It is not clear if 4665746657 is the only one with the shape 2a36+12^a 3^6 + 1 in its family. However, it lies outside the odd-mm hypothesis of [4] and [7], where they study number of the form 2npm+12^n p^m + 1 with prime pp. We plan to investigate the even-mm cases more to possibly put tractable bounds on prime divisors of Carmichael numbers of the form 2k3m+12^k 3^m + 1, and provide some more underlying structure to Carmichael numbers in the near future.

University of Bath, Faculty of Science, Department of Computer Science, Claverton Down, BA2 7AY, United Kingdom

Email address: {jlr85, aku21}@bath.ac.uk

References

  1. [1]Adel Alahmadi and Florian Luca. There are no Carmichael numbers of the form 2ⁿp + 1 with p prime. Comptes Rendus Mathématique, 360:1177–1181, 2022.DOI
  2. [2]Javier Cilleruelo, Florian Luca, and Amalia Pizarro-Madariaga. Carmichael numbers in the sequence (2ⁿk + 1)ₙ≥₁. Mathematics of Computation, 85(297):357–377, 2016.
  3. [3]Alwin Reinhold Korselt. Problème chinois. L’Intermédiaire des Mathématiciens, 6:142–143, 1899.
  4. [4]Florian Luca. On Carmichael numbers of the form 2ⁿpᵐ + 1, 2026. Preprint.
  5. [5]Florian Luca. Yet another curious property of 1729. The Ramanujan Journal, 70(4):74, 2026.DOI
  6. [6]Florian Luca and Jean Lucien Randrianantેનaina. There is no Carmichael number of the form 2ⁿp² + 1 with p prime. Integers, 23:A51, 2023. 15 pp.DOI
  7. [7]Pagdame Tiebekabe. Carmichael numbers of the form 2ⁿpᵐ + 1 with odd exponent m: refinements of a theorem of Florian Luca, a general independence lemma, and a computational study, 2026. Preprint.DOI

Paper details

vlnc:W_7zwtvn7h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents