betaFeedback

WorksMathematics

A Korselt Characterization of Carmichael Numbers of the Form (aCn+1)(aCn+1+1)(aCn+2+1)(aC_n+1)(aC_{n+1}+1)(aC_{n+2}+1)

Abstract

We study products N=(aCn+1)(aCn+1+1)(aCn+2+1), N=(aC_n+1)(aC_{n+1}+1)(aC_{n+2}+1), where (Cn)(C_n) is the Lucas–balancing sequence. Under the assumption that all three factors are prime, we give a necessary and sufficient condition for NN to be a Carmichael number: this happens precisely when nn is even and a=kCn+1a=kC_{n+1} for a positive integer kk satisfying 48k≡7(modCnCn+2). 48k\equiv 7\pmod{C_nC_{n+2}}. We derive further congruence restrictions, an explicit parametrization of the integer solutions of the resulting congruence, a lower bound for kk, and a divisibility relation involving the middle prime factor. The characterization is conditional on the primality of the three factors and does not assert that such prime triples exist for infinitely many parameters.

Introduction

A composite positive integer NN is called a Carmichael number if

bN−1≡1(modN)b^{N-1} \equiv1 \pmod{N}

for every integer bb relatively prime to NN. We use Korselt’s criterion: a composite positive integer NN is a Carmichael number if and only if it is square-free and p−1∣N−1p-1 \mid N-1 for every prime divisor pp of NN.

The Lucas–balancing numbers were introduced by Panda [11] in terms of the balancing numbers (Bn)n≥0(B_n)_{n\geq0}, originally studied by Behera and Panda [4]. They are defined by Cn=8Bn2+1C_n=\sqrt{8B_n^2+1} and satisfy the recurrence

C0=1,C1=3,Cn+2=6Cn+1−Cn,n≥0.C_0=1,\qquad C_1=3,\qquad C_{n+2}=6C_{n+1}-C_n,\qquad n\geq0.

Carmichael numbers have been studied since the early works of Korselt [8] and Carmichael [5]. Erdős and Odlyzko [7] investigated the density of odd integers related to primes and powers of 2. A major breakthrough came with Alford, Granville, and Pomerance [2], who proved that infinitely many Carmichael numbers exist. Subsequent studies have addressed their distribution and arithmetic properties. Harman [9] investigated their counting function, while Wright [12] established nonexistence results for certain classes of Carmichael numbers. Further contributions include the work of Banks et al. [3] and Cilleruelo, Luca, and Pizarro [6]. More recently, Alahmadi and Luca [1] proved that no Carmichael number can be of the form 2np+12^n p+1, where pp is prime. Advances in computational enumeration were reported by Shallue and Webster [10].

In this paper, we apply Korselt’s criterion to products of three consecutive terms of the Lucas–balancing sequence. Throughout, we consider

N=(aCn+1)(aCn+1+1)(aCn+2+1),a,n≥1,N=(aC_n+1)(aC_{n+1}+1)(aC_{n+2}+1),\qquad a,n\geq1,

assuming that all three factors are prime. Our main result gives an exact characterization of when NN is a Carmichael number.

Theorem 1. Let a,n≥1a,n\geq1, and suppose that

aCn+1,aCn+1+1,aCn+2+1aC_n+1,\qquad aC_{n+1}+1,\qquad aC_{n+2}+1

are prime. Then

N=(aCn+1)(aCn+1+1)(aCn+2+1)N=(aC_n+1)(aC_{n+1}+1)(aC_{n+2}+1)

is a Carmichael number if and only if nn is even and there exists an integer k≥1k\geq1 such that

a=kCn+1,48k≡7(modCnCn+2).a=kC_{n+1},\qquad48k\equiv7\pmod{C_nC_{n+2}}.

In particular, odd indices are impossible under the three-prime assumption.

Elementary identities

We establish several elementary properties of the sequence.

Lemma 1. The sequence (Cj)j≥0(C_j)_{j\geq0} consists of positive odd integers and is strictly increasing.

Proof. The initial terms satisfy C1>C0>0C_1 > C_0 > 0. If Cj+1>Cj>0C_{j+1} > C_j > 0, then

Cj+2=6Cj+1−Cj>5Cj+1>Cj+1.C_{j+2} = 6C_{j+1} - C_j > 5C_{j+1} > C_{j+1}.

Positivity and strict increase follow by induction. Both initial terms are odd, and the recurrence shows that every subsequent term is odd. □

Lemma 2. For every j≥0j \geq0,

gcd⁡(Cj,Cj+1)=1\gcd(C_j,C_{j+1}) = 1

and

CjCj+2−Cj+12=8.C_jC_{j+2} - C_{j+1}^{2} = 8.

Proof. The recurrence gives

gcd⁡(Cj+1,Cj+2)=gcd⁡(Cj+1,6Cj+1−Cj)=gcd⁡(Cj+1,Cj).\gcd(C_{j+1},C_{j+2}) = \gcd(C_{j+1},6C_{j+1} - C_j) = \gcd(C_{j+1},C_j).

Since gcd⁡(C0,C1)=1\gcd(C_0,C_1) = 1, the first assertion follows.

For the second assertion, put

Ej=CjCj+2−Cj+12.E_j = C_jC_{j+2} - C_{j+1}^{2}.

Using Cj+3=6Cj+2−Cj+1C_{j+3} = 6C_{j+2} - C_{j+1}, we obtain

Ej+1=Cj+1Cj+3−Cj+22=Cj+1(6Cj+2−Cj+1)−Cj+22=(6Cj+1−Cj+2)Cj+2−Cj+12=CjCj+2−Cj+12=Ej.\begin{aligned} E_{j+1} &= C_{j+1}C_{j+3} - C_{j+2}^{2} \\ &= C_{j+1}(6C_{j+2} - C_{j+1}) - C_{j+2}^{2} \\ &= (6C_{j+1} - C_{j+2})C_{j+2} - C_{j+1}^{2} \\ &= C_jC_{j+2} - C_{j+1}^{2} \\ &= E_j. \end{aligned}

Hence EjE_j is constant. Since C2=17C_2 = 17,

E0=C0C2−C12=17−9=8.E_0 = C_0C_2 - C_1^{2} = 17 - 9 = 8.

Lemma 3. For every j≥0j \geq0,

3∣Cj⟺j is odd.3 \mid C_j \Longleftrightarrow j\text{ is odd}.

Moreover,

gcd⁡(Cj,Cj+2)={1,j is even,3,j is odd.\operatorname{gcd}(C_j,C_{j+2}) = \begin{cases} 1, & j\text{ is even},\\ 3, & j\text{ is odd}. \end{cases}

Proof. Modulo 3, the recurrence becomes

Cj+2≡−Cj(mod3).C_{j+2} \equiv-C_j \pmod{3}.

Starting from C0≡1C_0 \equiv1 and C1≡0(mod3)C_1 \equiv0 \pmod{3}, we obtain

C2r≡(−1)r(mod3),C2r+1≡0(mod3).C_{2r} \equiv(-1)^r \pmod{3}, \qquad C_{2r+1} \equiv0 \pmod{3}.

By Lemma 2,

gcd⁡(Cj,Cj+2)=gcd⁡(Cj,6Cj+1)=gcd⁡(Cj,6).\begin{aligned} \operatorname{gcd}(C_j,C_{j+2})=\operatorname{gcd}(C_j,6C_{j+1}) \\ &=\operatorname{gcd}(C_j,6). \end{aligned}

Since every CjC_j is odd, the claimed formula follows. □

Lemma 4. For every j≥0j \ge0,

C2j≡1(mod8),C2j+1≡3(mod8).C_{2j} \equiv1 \pmod{8}, \qquad C_{2j+1} \equiv3 \pmod{8}.

Proof. The assertions hold for j=0j=0, since C0=1C_0=1 and C1=3C_1=3. Assume that

C2j≡1(mod8),C2j+1≡3(mod8).C_{2j} \equiv1 \pmod{8}, \qquad C_{2j+1} \equiv3 \pmod{8}.

Then, using the recurrence,

C2j+2=6C2j+1−C2j≡18−1≡1(mod8),C_{2j+2}=6C_{2j+1}-C_{2j}\equiv18-1\equiv1 \pmod{8},

and

C2j+3=6C2j+2−C2j+1≡6−3≡3(mod8).C_{2j+3}=6C_{2j+2}-C_{2j+1}\equiv6-3\equiv3 \pmod{8}.

The result follows by induction. □

Proof of the main theorem

We apply Korselt’s criterion. Since

Cn<Cn+1<Cn+2C_n<C_{n+1}<C_{n+2}

by Lemma 1, and since a≥1a \ge1, the three assumed prime factors of NN are distinct. Hence NN is square-free.

Since the three factors of NN are distinct primes, NN is a Carmichael number if and only if

aCn∣N−1,aCn+1∣N−1,aCn+2∣N−1.aC_n \mid N-1, \qquad aC_{n+1} \mid N-1, \qquad aC_{n+2} \mid N-1.

Expanding and collecting terms according to powers of aa, we obtain

N=(aCn+1)(aCn+1+1)(aCn+2+1)=1+a(Cn+Cn+1+Cn+2)+a2(CnCn+1+CnCn+2+Cn+1Cn+2)+a3CnCn+1Cn+2.\begin{aligned} N &= (aC_n+1)(aC_{n+1}+1)(aC_{n+2}+1)\\ &= 1+a(C_n+C_{n+1}+C_{n+2})\\ &\quad+a^2(C_nC_{n+1}+C_nC_{n+2}+C_{n+1}C_{n+2})\\ &\quad+a^3C_nC_{n+1}C_{n+2}. \end{aligned}

Hence,

N−1=a[Cn+Cn+1+Cn+2+a(CnCn+1+CnCn+2+Cn+1Cn+2)+a2CnCn+1Cn+2].N-1=a\left[C_n+C_{n+1}+C_{n+2} +a(C_nC_{n+1}+C_nC_{n+2}+C_{n+1}C_{n+2}) +a^2C_nC_{n+1}C_{n+2}\right].

For convenience, define

T=Cn+Cn+1+Cn+2+a(CnCn+1+CnCn+2+Cn+1Cn+2)+a2CnCn+1Cn+2.T=C_n+C_{n+1}+C_{n+2} +a(C_nC_{n+1}+C_nC_{n+2}+C_{n+1}C_{n+2}) +a^2C_nC_{n+1}C_{n+2}.

Thus

N−1=aT.N-1=aT.

Since N−1=aTN-1=aT and a≥1a\ge1, Korselt’s criterion is equivalent to

Cn∣T,Cn+1∣T,Cn+2∣T.(1)C_n\mid T,\qquad C_{n+1}\mid T,\qquad C_{n+2}\mid T. \tag*{(1)}

We now derive these divisibility conditions explicitly.

Step 1: The condition involving Cn+1C_{n+1}.

Reducing TT modulo Cn+1C_{n+1} gives

T≡Cn+Cn+2+aCnCn+2(modCn+1).T\equiv C_n+C_{n+2}+aC_nC_{n+2}\pmod{C_{n+1}}.

By the recurrence relation,

Cn+2=6Cn+1−Cn,C_{n+2}=6C_{n+1}-C_n,

so that

Cn+2≡−Cn(modCn+1).C_{n+2}\equiv-C_n\pmod{C_{n+1}}.

It follows that

T=Cn−Cn−aCn2≡−aCn2(modCn+1).\begin{aligned} T&=C_n-C_n-aC_n^2\\ &\equiv-aC_n^2\pmod{C_{n+1}}. \end{aligned}

The consecutive terms are coprime:

gcd⁡(Cn,Cn+1)=1.\gcd(C_n,C_{n+1})=1.

Hence

Cn+1∣T⟺Cn+1∣aCn2⟺Cn+1∣a.C_{n+1}\mid T \Longleftrightarrow C_{n+1}\mid aC_n^2 \Longleftrightarrow C_{n+1}\mid a.

Therefore, the middle divisibility condition in (1) is equivalent to the existence of an integer k≥1k\ge1 such that

a=kCn+1.(2)a=kC_{n+1}. \tag*{(2)}

Step 2: The conditions involving CnC_n and Cn+2C_{n+2}.

Reducing TT modulo CnC_n, all terms containing CnC_n vanish, and we obtain

T≡Cn+1+Cn+2+aCn+1Cn+2(modCn).T\equiv C_{n+1}+C_{n+2}+aC_{n+1}C_{n+2}\pmod{C_n}.

Since

Cn+2≡6Cn+1(modCn),C_{n+2}\equiv6C_{n+1}\pmod{C_n},

we get

T≡Cn+1(7+6aCn+1)(modCn).T\equiv C_{n+1}(7+6aC_{n+1})\pmod{C_n}.

As gcd⁡(Cn,Cn+1)=1\gcd(C_n,C_{n+1})=1, this yields

Cn∣T⟺Cn∣7+6aCn+1.(3)C_n\mid T \Longleftrightarrow C_n\mid7+6aC_{n+1}. \tag*{(3)}

Similarly, reducing TT modulo Cn+2C_{n+2} gives

T≡Cn+Cn+1+aCnCn+1(modCn+2).T\equiv C_n+C_{n+1}+aC_nC_{n+1}\pmod{C_{n+2}}.

Using

Cn≡6Cn+1(modCn+2),C_n\equiv6C_{n+1}\pmod{C_{n+2}},

we obtain

T≡Cn+1(7+6aCn+1)(modCn+2).T\equiv C_{n+1}(7+6aC_{n+1})\pmod{C_{n+2}}.

Since gcd⁡(Cn+1,Cn+2)=1\gcd(C_{n+1},C_{n+2})=1, it follows that

Cn+2∣T⟺Cn+2∣7+6aCn+1.(4)C_{n+2}\mid T \Longleftrightarrow C_{n+2}\mid7+6aC_{n+1}. \tag*{(4)}

Combining (3) and (4), the two outer divisibility conditions are equivalent to

Cn∣7+6aCn+1,Cn+2∣7+6aCn+1.(5)C_n\mid7+6aC_{n+1},\qquad C_{n+2}\mid7+6aC_{n+1}. \tag*{(5)}

Step 3: The parity of nn.

The sequence satisfies the identity

CnCn+2−Cn+12=8.(6)C_nC_{n+2}-C_{n+1}^2=8. \tag*{(6)}

Indeed, this identity is Lemma 2.

Substituting a=kCn+1a=kC_{n+1} from (2) into (5), we find

Cn∣7+6kCn+12,Cn+2∣7+6kCn+12.C_n \mid7+6kC_{n+1}^{2}, \qquad C_{n+2} \mid7+6kC_{n+1}^{2}.

By (6),

7+6kCn+12=7+6k(CnCn+2−8)=6kCnCn+2+7−48k.\begin{aligned} 7+6kC_{n+1}^{2} &= 7+6k(C_nC_{n+2}-8)\\ &=6kC_nC_{n+2}+7-48k. \end{aligned}

Therefore, (5) is equivalent to

Cn∣48k−7,Cn+2∣48k−7.(7)C_n \mid48k-7,\qquad C_{n+2}\mid48k-7. \tag*{(7)}

We now show that nn must be even. By Lemma 3,

3∣Cj⟺j is odd.3\mid C_j \Longleftrightarrow j\text{ is odd}.

If nn were odd, then both CnC_n and Cn+2C_{n+2} would be divisible by 3. By (7), this would imply

3∣48k−7.3\mid48k-7.

But

48k−7≡−1(mod3),48k-7\equiv-1\pmod{3},

which is impossible. Hence

n is even.(8)n\text{ is even}. \tag*{(8)}

Step 4: Combining the two congruences.

For even nn, both CnC_n and Cn+2C_{n+2} are odd. By Lemma 2,

gcd⁡(Cn,Cn+2)∣8.\gcd(C_n,C_{n+2})\mid8.

Since their greatest common divisor is odd, we conclude that

gcd⁡(Cn,Cn+2)=1.\gcd(C_n,C_{n+2})=1.

Consequently, the two divisibilities in (7) are equivalent to

48k≡7(modCnCn+2).(9)48k\equiv7\pmod{C_nC_{n+2}}. \tag*{(9)}

This proves the necessity of all the stated conditions.

Step 5: Sufficiency.

Conversely, suppose that nn is even and that

a=kCn+1,48k≡7(modCnCn+2)a=kC_{n+1},\qquad48k\equiv7\pmod{C_nC_{n+2}}

for some integer k≥1k\ge1.

We prove that all three divisibilities in (1) hold. First, since Cn+1∣aC_{n+1} \mid a, the calculation in Step 1 gives

T≡−aCn2≡0(modCn+1).T \equiv-aC_n^2 \equiv0 \pmod{C_{n+1}}.

Thus

Cn+1∣T.C_{n+1} \mid T.

Next, the congruence in (9), together with identity (6), gives

7+6aCn+1=7+6kCn+12=6kCnCn+2+7−48k≡0(modCnCn+2).\begin{aligned} 7+6aC_{n+1} &= 7+6kC_{n+1}^{2} \\ &= 6kC_nC_{n+2}+7-48k \\ &\equiv0 \pmod{C_nC_{n+2}}. \end{aligned}

In particular,

Cn∣7+6aCn+1,Cn+2∣7+6aCn+1.C_n \mid7+6aC_{n+1}, \qquad C_{n+2} \mid7+6aC_{n+1}.

By the equivalences established in Step 2, we obtain

Cn∣T,Cn+2∣T.C_n \mid T, \qquad C_{n+2} \mid T.

Therefore,

Cn∣T,Cn+1∣T,Cn+2∣T.C_n \mid T, \qquad C_{n+1} \mid T, \qquad C_{n+2} \mid T.

Since N−1=aTN-1=aT, it follows that

aCn∣N−1,aCn+1∣N−1,aCn+2∣N−1.aC_n \mid N-1, \qquad aC_{n+1} \mid N-1, \qquad aC_{n+2} \mid N-1.

The three factors of NN are distinct primes by hypothesis, so NN is square-free. Korselt’s criterion now implies that NN is a Carmichael number. The proof is complete.

Further arithmetic consequences

Lemma 5. For every j≥0j \ge0,

C2j≡{1(mod48),j is even,17(mod48),j is odd,C2j+1≡3(mod48).C_{2j} \equiv \begin{cases} 1 \pmod{48}, & j\text{ is even},\\ 17 \pmod{48}, & j\text{ is odd}, \end{cases} \qquad C_{2j+1} \equiv3 \pmod{48}.

In particular, for every even n≥2n \ge2,

CnCn+2≡17(mod48).C_nC_{n+2} \equiv17 \pmod{48}.

Proof. We prove the residue pattern by induction on jj. For j=0j=0,

C0=1≡1(mod48),C1=3≡3(mod48).C_0=1\equiv1 \pmod{48}, \qquad C_1=3\equiv3 \pmod{48}.

Assume that

C2j≡r(mod48),C2j+1≡3(mod48).C_{2j}\equiv r \pmod{48}, \qquad C_{2j+1}\equiv3 \pmod{48}.

where r∈{1,17}r \in\{1,17\}. Then

C2j+2=6C2j+1−C2j≡18−r(mod48).C_{2j+2}=6C_{2j+1}-C_{2j}\equiv18-r \pmod{48}.

Thus r=1r=1 gives C2j+2≡17(mod48)C_{2j+2}\equiv17\pmod{48}, while r=17r=17 gives C2j+2≡1(mod48)C_{2j+2}\equiv1\pmod{48}. Moreover,

C2j+3=6C2j+2−C2j+1=6(18−r)−3≡3(mod48),C_{2j+3}=6C_{2j+2}-C_{2j+1}=6(18-r)-3\equiv3\pmod{48},

because r∈{1,17}r\in\{1,17\} implies 108−6r≡6(mod48)108-6r\equiv6\pmod{48}. Hence, by induction,

C2j≡1,17,1,17,…(mod48),C2j+1≡3(mod48).C_{2j}\equiv1,17,1,17,\ldots\pmod{48},\qquad C_{2j+1}\equiv3\pmod{48}.

For even nn, the residues of CnC_n and Cn+2C_{n+2} are 1 and 17 in some order. Their product is therefore congruent to 17 modulo 48. □

Theorem 2. Under the hypotheses of Theorem 1, if NN is Carmichael, then

48k−7CnCn+2=25(mod48).\frac{48k-7}{C_nC_{n+2}}=25\pmod{48}.

Proof. By Theorem 1, nn is even, a=kCn+1a=kC_{n+1} for some integer k≥1k\ge1, and

q=48k−7CnCn+2q=\frac{48k-7}{C_nC_{n+2}}

is an integer. Since k≥1k\ge1, we have 48k−7>048k-7>0; also CnCn+2>0C_nC_{n+2}>0. Hence qq is a positive integer.

By Lemma 5,

CnCn+2≡17(mod48).C_nC_{n+2}\equiv17\pmod{48}.

Since 48k−7≡41(mod48)48k-7\equiv41\pmod{48}, we get

17q≡41(mod48).17q\equiv41\pmod{48}.

As 172≡1(mod48)17^2\equiv1\pmod{48}, multiplication by 17 yields

q≡17⋅41≡25(mod48).q\equiv17\cdot41\equiv25\pmod{48}.

□

Theorem 3 (Divisibility restriction on the middle prime). Under the hypotheses of Theorem 1, suppose that N=p0p1p2N=p_0p_1p_2 is Carmichael. Put

M=CnCn+2,q=48k−7M,M=C_nC_{n+2},\qquad q=\frac{48k-7}{M},

where a=kCn+1a=kC_{n+1}. Then

M∣6p1+1M\mid6p_1+1

and

6p1+1M=6k−q.\frac{6p_1+1}{M}=6k-q.

In particular, the quotient on the left is a positive integer.

Proof. By Theorem 1, we have

a=kCn+1,M∣48k−7.a = kC_{n+1}, \qquad M \mid48k-7.

The identity

Cn+12=CnCn+2−8=M−8C_{n+1}^{2}=C_nC_{n+2}-8=M-8

gives

6p1+1=6(aCn+1+1)+1=6kCn+12+7=6k(M−8)+7=6kM−(48k−7).\begin{aligned} 6p_1+1 &= 6(aC_{n+1}+1)+1\\ &=6kC_{n+1}^{2}+7\\ &=6k(M-8)+7\\ &=6kM-(48k-7). \end{aligned}

Since M∣48k−7M \mid48k-7, we obtain M∣6p1+1M \mid6p_1+1. Dividing the displayed identity by MM yields

6p1+1M=6k−48k−7M=6k−q.\frac{6p_1+1}{M}=6k-\frac{48k-7}{M}=6k-q.

The quotient is positive because 6p1+1>06p_1+1>0 and M>0M>0.

Corollary 1. Under the hypotheses of Theorem 2,

k≥25CnCn+2+748k\geq\frac{25C_nC_{n+2}+7}{48}

and

a≥Cn+1(25CnCn+2+7)48.a\geq\frac{C_{n+1}(25C_nC_{n+2}+7)}{48}.

Proof. By Theorem 2, the integer

q=48k−7CnCn+2q=\frac{48k-7}{C_nC_{n+2}}

is positive and congruent to 25 modulo 48. Hence q≥25q\geq25. Thus

48k−7≥25CnCn+2.48k-7\geq25C_nC_{n+2}.

Rearranging gives the first inequality; the second follows from a=kCn+1a=kC_{n+1}.

Theorem 4. Fix an even integer n≥2n\geq2 and put

M=CnCn+2.M=C_nC_{n+2}.

Every positive integer kk satisfying

M∣48k−7M\mid48k-7

has the form

k=25M+748+tM,t∈Z≥0.\boxed{k=\frac{25M+7}{48}+tM,\qquad t\in\mathbb{Z}_{\geq0}.}

Among these values, kk is even if and only if

t≡25M+748(mod2).t\equiv\frac{25M+7}{48}\pmod{2}.

Proof. By Lemma 5, M≡17(mod48)M \equiv17 \pmod{48}. Hence

25M+7≡25⋅17+7≡0(mod48),25M+7 \equiv25\cdot17+7 \equiv0 \pmod{48},

so

k0=25M+748k_0=\frac{25M+7}{48}

is a positive integer. Moreover,

k0=25M+748<M.k_0=\frac{25M+7}{48}<M.

If M∣48k−7M\mid48k-7, then

48k−7=qM48k-7=qM

for some integer qq. Reducing modulo 4848 shows that q≡25(mod48)q\equiv25\pmod{48}, so q=25+48tq=25+48t for an integer tt. It follows that

k=7+qM48=25M+748+tM=k0+tM.k=\frac{7+qM}{48}=\frac{25M+7}{48}+tM=k_0+tM.

Since 0<k0<M0<k_0<M, positivity of kk is equivalent to t≥0t\ge0.

Finally, MM is odd, so

k=k0+tM≡k0+t(mod2).k=k_0+tM\equiv k_0+t\pmod{2}.

Thus kk is even if and only if t≡k0(mod2)t\equiv k_0\pmod{2}, as claimed. This parametrizes the positive integer solutions of the congruence only; the primality of the three corresponding factors must still be checked separately.

Proposition 1 (Further congruence restrictions). If NN is Carmichael under the hypotheses of Theorem 1, then its prime factors pi=aCn+i+1p_i=aC_{n+i}+1 satisfy

pi≡1(mod6)(i=0,1,2),p_i\equiv1\pmod{6}\qquad(i=0,1,2),

and the two outer factors satisfy

p0≡p2(mod8).p_0\equiv p_2\pmod{8}.

Proof. Theorem 1 gives a=kCn+1a=kC_{n+1} with nn even. By Lemma 3, 3∣Cn+13\mid C_{n+1}, so 3∣a3\mid a. Also, aa must be even: if it were odd, then each aCn+i+1aC_{n+i}+1 would be an even integer greater than 2, contradicting primality. Thus 6∣a6\mid a and

pi=aCn+i+1≡1(mod6).p_i=aC_{n+i}+1\equiv1\pmod{6}.

Since nn is even, Lemma 4 gives Cn≡Cn+2≡1(mod8)C_n\equiv C_{n+2}\equiv1\pmod{8}. Therefore

p0=aCn+1≡a+1≡aCn+2+1=p2(mod8).p_0=aC_n+1\equiv a+1\equiv aC_{n+2}+1=p_2\pmod{8}.

Corollary 2. Under the three-prime assumption, if aa is a positive power of 2, then NN is not Carmichael.

Proof. Theorem 1 requires Cn+1∣aC_{n+1}\mid a. But Cn+1C_{n+1} is odd and greater than 1 for n≥1n\ge1, so it cannot divide a power of 2. □

An explicit example

Take n=2n=2. Then

C2=17,C3=99,C4=577,C_2=17,\qquad C_3=99,\qquad C_4=577,

and

M=C2C4=17⋅577=9809.M=C_2C_4=17\cdot577=9809.

The congruence 48k≡7(mod9809)48k\equiv7\pmod{9809} is equivalent to

k≡5109(mod9809).k\equiv5109\pmod{9809}.

Since kk must be even, we may write

k=14918+19618s,s≥0.k=14918+19618s,\qquad s\geq0.

Taking s=363s=363 gives

k=7136252,a=99k=706488948.k=7136252,\qquad a=99k=706488948.

The corresponding factors are

p0=aC2+1=12010312117,p_0=aC_2+1=12010312117,
p1=aC3+1=69942405853,p_1=aC_3+1=69942405853,
p2=aC4+1=407644122997.p_2=aC_4+1=407644122997.

For this example, the divisibility quotient is

48k−7C2C4=3425400899809=34921,\frac{48k-7}{C_2C_4}=\frac{342540089}{9809}=34921,

and 34921≡25(mod48)34921\equiv25\pmod{48}, as required by Theorem 2. The primality of the three displayed factors is verified in Appendix § 6. This computation concerns only the particular example and is not used in the proof of Theorem 1.

Verification of the example

For reproducibility, the primality of the three factors in § 5 can be checked using the following Python/SymPy commands:

from sympy import isprime

p0 = 12010312117
p1 = 69942405853
p2 = 407644122997
assert isprime(p0)
assert isprime(p1)
assert isprime(p2)

This verifies the primality claims in the displayed example. It does not form part of the proof of the main theorem.

Declarations

Conflict of interest. The author declares that there is no conflict of interest.

References

  1. [1]A. Alahmadi and F. Luca, “There are no Carmichael numbers of the form 2^n p + 1 with p prime,” Comptes Rendus Mathématique, vol. 360, pp. 1177–1181, 2022.DOI
  2. [2]W. R. Alford, A. Granville, and C. Pomerance, “There are infinitely many Carmichael numbers,” Annals of Mathematics, vol. 139, no. 3, pp. 703–722, 1994.DOI
  3. [3]W. D. Banks, C. Finch, F. Luca, C. Pomerance, and P. Stănică, “Sierpiński and Carmichael numbers,” Transactions of the American Mathematical Society, vol. 367, no. 1, pp. 355–376, 2015.DOI
  4. [4]A. Behera and G. K. Panda, “On the square roots of triangular numbers,” The Fibonacci Quarterly, vol. 37, no. 2, pp. 98–105, 1999.
  5. [5]R. D. Carmichael, “Note on a new number theory function,” Bulletin of the American Mathematical Society, vol. 16, no. 5, pp. 232–238, 1910.DOI
  6. [6]J. Cilleruelo, F. Luca, and A. Pizarro, “Carmichael numbers in the sequence (2^k + 1)n≥1,” Mathematics of Computation, vol. 85, no. 297, pp. 357–377, 2016.
  7. [7]P. Erdős and A. M. Odlyzko, “On the density of odd integers of the form (p − 1)2−n and related questions,” Journal of Number Theory, vol. 11, pp. 257–263, 1979.DOI
  8. [8]A. Korselt, “Problème chinois,” L’Intermédiaire des Mathématiciens, vol. 6, pp. 142–143, 1899.
  9. [9]G. Harman, “On the number of Carmichael numbers up to x,” Bulletin of the London Mathematical Society, vol. 37, no. 5, pp. 641–650, 2005.DOI
  10. [10]A. Shallue and J. Webster, “Advances in tabulating Carmichael numbers,” Research in Number Theory, vol. 11, no. 1, article 8, 2025. doi: 10.1007/s40993-024-00598-3.DOI
  11. [11]G. K. Panda, “Some fascinating properties of balancing numbers,” Proceedings of the Eleventh International Conference on Fibonacci Numbers and Their Applications, pp. 185–189, 2009.
  12. [12]T. Wright, “The impossibility of certain types of Carmichael numbers,” Integers, vol. 12, no. 5, pp. 951–964, 2012.DOI

Paper details

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

views · 0

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