WorksMathematics
One more curious property of : The only Carmichael number of the form with prime
Abstract
Florian Luca recently proved that if is a Carmichael number for some prime and integer , then . Here we complete the cubic classification by proving that , Hardy–Ramanujan taxicab number, is the only Carmichael number of the form with prime and . The proof identifies the unique possible multiplicatively dependent prime factor, sharpens the known bound on Fermat prime factors of from to , derives the explicit bound , and concludes with a short sieve requiring neither factorisation nor primality testing.
Introduction
A Carmichael number is a composite integer such that for every integer . Korselt’s criterion [3] gives the following characterisation: a composite integer is Carmichael if and only if is square-free and for every prime factor of . 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 , the sequence contains only finitely many Carmichael numbers, and that the smallest element of the set
is 27. In particular, for and , we have .
Alahmadi and Luca [1] subsequently proved that contains no prime, and Luca and Randrianantenaina [6] proved that contains no square of a prime. The cubic case is different, since belongs to .
Luca [5] addressed the prime part of the cubic case and proved the following result.
Theorem 1 (Luca [5]). If is prime and is Carmichael for some , then .
Thus any Carmichael number of the form must occur in the sequence .
Our main result completes the cubic classification.
Theorem 2. For , is a Carmichael number if and only if . Consequently,
is the unique Carmichael number in the sequence .
Combining Theorem 1 and Theorem 2 gives the complete classification.
Corollary 1. For a prime and integer , is Carmichael if and only if .
In 2026, Luca [4] proved that, for every fixed odd , there are only finitely many primes with ; the resulting bound on is ineffective. Tiebekabe [7] made several steps of [2, 4] explicit. In particular, if is odd, and is Carmichael, then , and every prime factor of has multiplicatively independent of [7 Theorems 1.1 and 1.3]. He also reported an exhaustive search showing that 1729 is the only Carmichael number with odd and [7 Theorem 1.4].
Both structural results just quoted require , so they do not apply to the case treated here. This exclusion is genuine: for 1729, the prime factor 13 satisfies and , so a multiplicatively dependent prime factor occurs; see Lemma 1. Moreover, the restriction covers only , whereas Theorem 2 covers all .
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 . § 3 presents a sharper version of the bound in [2 Lemma 2] for Fermat prime factors. In § 4, we first bound the largest exponent that can yield a Carmichael number , and then we give explicit bounds for the size of prime factors of . § 5 has the sieve for the divisors of 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 . Assume from now on, unless stated otherwise, that is Carmichael. If is prime, Korselt’s criterion gives . Therefore every prime factor of has the form
We call the integers and multiplicatively dependent, if there exist positive integers such that
For we have , so must be a power of 2 and is a Fermat prime. For , we now determine when and can be multiplicatively dependent. In the analogous cubic problem with , Luca excludes this possibility [5 Section 2.1]; for 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 be prime, with . If and are multiplicatively dependent, then , and . Thus the only possible dependent prime factor is
Conversely, if , then ; if is prime, it is the unique dependent prime factor of .
Proof. If and are multiplicatively dependent, comparing the 2-adic and 3-adic valuations in (2) gives and , hence
Conversely, (4) gives , so it is equivalent to multiplicative dependence in the present setting.
If , then (4) gives and . This is a contradiction since is prime whereas is Carmichael and therefore composite.
If , then , so and for some . Put . Then and . Since and , we have . Thus , impossible because .
Finally, if , then (4) gives . If and , then
so divides . If is prime, then and , proving dependence. Uniqueness follows because is completely determined by . □
Note that possibility for the prime divisors of is ignored in Lemma 1. This is because forces , and later . This does not fit into the multiplicative dependence definition with positive and . We handle case next.
Eliminating Fermat Prime Factors
By [2 Lemma 2], every Fermat prime factor of is less than . For this gives the preliminary bound . The following elementary theorem sharpens to , and yields in the present case.
Theorem 3. Let be odd, , and let be a prime dividing . Then .
Proof. If , then . Assume , put , so that , and write with . From we obtain . Multiplying by and using gives
Assume, for a contradiction, that . Then and . If is even, (5) forces to be even and yields a contradiction. If is odd, (5) forces . If , then , a contradiction. If , then , so , contradicting .
Thus, for , the only possible Fermat prime factors of are 3, 5 and 17.
Theorem 3 has several useful consequences. First off, the bound is attained up to one unit for every Fermat prime . Indeed, let be a Fermat prime with , and set and . Then is odd and
Thus and .
Moreover, the theorem also improves the bound for the entire Fermat part. Let be the Fermat numbers, and suppose that is the largest Fermat prime dividing . Since , we have . Therefore, the product of the distinct Fermat prime divisors of satisfies
For comparison, [2 (15)] obtains from the earlier individual bound . In Luca’s cubic setting , this appears as ; see [5 Section 2.1]. Thus Theorem 3 improves the corresponding general Fermat part estimate from to .
To exemplify this, we look at our case . The earlier bound leaves 257 as an additional possible Fermat prime factor that must be excluded separately. Indeed, , so would imply , but , where is the smallest positive integer such that . A direct check of the powers modulo 257 shows that , where denotes the orbit of powers of 2 modulo 257. Hence . The sharper bound makes this additional check unnecessary.
Now we further investigate some properties of .
Lemma 2. Let . Then
i. ;
ii. if and only if ; and
iii. .
Proof. i. Obvious since .
ii. We have if and only if , since . As , this is equivalent to .
iii. Since and , we have if and only if . However, and the orbit of powers of 2 modulo 17 is (mod 17), which does not contain 5.
Theorem 4. If is Carmichael, then has no Fermat prime factor. In particular, every prime divisor of has in (1), and .
Proof. By Theorem 3 and Lemma 2, the only Fermat prime that can divide is 5. Indeed, and . Suppose that . Since is square-free, 5 occurs exactly once in its prime factorisation. Therefore every other prime divisor of is not a Fermat prime and, by (1), has the form with , implying . Reducing the prime factorisation of modulo 3 therefore gives , contradicting . Hence, has no Fermat prime factor. The final assertion follows from part (ii) of Lemma 2.
Bounding
Here we mostly follow the footsteps of [2] to find a sharper bound for of and the exponents of that appear in the representation of the prime divisors of . This enables us to limit the number of cases to consider for a proof of Theorem 2.
Let denote the product of all prime factors of such that and are multiplicatively independent. By Theorem 4, all these factors have . By Lemma 1, at most one prime factor, namely , is omitted from , and this can happen only when . Hence,
Lemma 3. Let , with , be an multiplicatively independent prime factor of . Then
Moreover, .
Proof. The relations and , together with , give and . Since is odd and , no prime divisor of can be 2 or 3. Thus , so both 2 and 3 are invertible modulo .
If , cubing the first congruence and substituting into the second gives . If , cubing the first congruence and squaring the second gives . If , direct substitution gives . These are exactly the three cases in (7).
Regardless of the choice of , if , then (7) shows that , which shows that these terms are multiplicatively dependent (4). Hence, . Since , the three cases also give .
Squaring (7) gives , and implies
On the other hand, we have , while Korselt’s criterion implies . Putting together, we see that
With these relations at hand, we derive a general bound for divisors , with odd, satisfying for some small . The argument refines the box-principle method of [2 Lemma 4], also used in [5 Section 2.1].
Lemma 4. Let be odd, put , let be a positive divisor of , and let satisfy . Put and . Then
In particular, .
Proof. If , there is nothing to prove, so assume . Since , we have ; also gives . Hence, . Moreover, , so .
Since , we have and . Thus, for ,
There are such pairs but only residue classes modulo . Hence, by the pigeonhole principle, there exist two distinct pairs and that satisfy . Since , it follows that .
After cancelling the common powers of 2 and , which are invertible modulo , we obtain , where
with , , and .
We have . Indeed, this is immediate if . If and , then ; since and , this forces and , contradicting the choice of distinct pairs. While bounding , we encounter two cases up to switching the order of the pairs and . If , then . Otherwise, we may assume and , and then , since . Thus . Since , we obtain , and (10) gives .
For , the following is immediate.
Corollary 2. If is an independent prime factor of the Carmichael number , then
In particular, .
Proof. Apply Lemma 4 with , and . Since (8) gives , we have . Taking base 2 logarithms yields the stated inequality.
We now bound the product of all independent prime factors of .
Lemma 5. For each with , let be the largest integer of the form not exceeding , and set
If , set . Then every independent prime factor of divides at least one of , and
Proof. Let be an independent prime factor of . By (9), for some and , and (8) gives . Hence, , so is defined. By maximality of the exponent of 2 in , we have . Therefore , and since , we obtain .
Thus every prime factor of divides at least one . Since is squarefree, , 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 is Carmichael, then . If, in addition, , then .
Proof. Let and .
If , then (6) and Lemma 5 give . Taking logarithms to base 2 gives . The larger root of the corresponding quadratic is approximately . The inequality and the larger root imply . Hence, ; since , the value 1215 is excluded and therefore .
If , then (6) gives . Put . Since and , we have . Combining this with Lemma 5 gives
Taking logarithms to base 2 yields . Similarly, the larger root is approximately , and we get . Since , it follows that .
Since is now bounded, Corollary 2 gives an explicit bound on the exponent of every independent prime factor. If , then , hence , so . If , then , hence , so . In the latter case, there may also be the unique dependent prime factor . Notice that any multiplicatively dependent term candidate is known explicitly and also bounded since 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],
is effective but very large in the present case. For , where and , it gives .
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 . For the argument gives, for each of the four order classes,
and hence . If there is no dependent factor, then , so , which gives .
If a dependent factor occurs, then and . In this case , so , which gives and hence, since , . The values 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 divides a Carmichael number , with , , and multiplicatively independent of , then whenever . For and , this gives , hence . If , then and trivially . Thus covers all independent prime factors in the range .
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 and . For , since , we have . Thus the new argument gives , improving the estimate on above. Likewise, Corollary 2 gives instead of . Together with the treatment of the dependent factor, these improvements reduce the global range to and give for every independent prime factor.
For comparison, the explicit estimate in [7 Theorem 1.1(ii)] is obtained under the hypothesis . It therefore does not cover the exceptional cubic case considered here, where .
A Factorisation Free Sieve
For each admissible , define and
If , we additionally include in .
Proposition 2. If is Carmichael, then every prime divisor of belongs to . Furthermore, if , then .
Proof. Let be prime. By (1) and Theorem 4, with .
Suppose first that and are multiplicatively independent. By Corollary 2, ; since is an integer, . As also , we have . Finally, and because is composite, so .
If and are dependent, then Lemma 1 gives and , which is included in . Thus every prime divisor of belongs to .
Since is Carmichael, it is square-free. Hence, is the product of its distinct prime divisors. Every such prime belongs to and therefore divides , so . □
Proof of Theorem 2. Proposition 2 gives a finite sieve requiring neither factorisation of nor primality tests for the elements of : any admissible for which cannot yield a Carmichael number. By Proposition 1, it suffices to consider with , and with . For each such we computed with exact integer arithmetic. The only surviving value is
for which
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 with and with included whenever . Again, the only surviving value is . 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 is Carmichael, then Theorem 1 gives and Theorem 2 gives . Conversely, is square-free and , and all divide , so is Carmichael by Korselt’s criterion. □
Outlook
In [5], Luca studies primes . In § 2, He describes how 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 , the factor is precisely the dependent prime factor (of Lemma 1 since ), while and are independent. We observe that the exact structure that we see in § 2 occurs in another similar Carmichael number . This was also noticed in [7]. Here is the unique dependent factor. It is not clear if is the only one with the shape in its family. However, it lies outside the odd- hypothesis of [4] and [7], where they study number of the form with prime . We plan to investigate the even- cases more to possibly put tractable bounds on prime divisors of Carmichael numbers of the form , 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]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]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]Alwin Reinhold Korselt. Problème chinois. L’Intermédiaire des Mathématiciens, 6:142–143, 1899.
- [4]Florian Luca. On Carmichael numbers of the form 2ⁿpᵐ + 1, 2026. Preprint.
- [5]Florian Luca. Yet another curious property of 1729. The Ramanujan Journal, 70(4):74, 2026.DOI
- [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]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