Problems & Puzzles: Problems

Problem 57.  Carmichael numbers c & 2c+1.

Emmanuel Vantieghem share with us the following problem:

Q1. Carmichael numbers  c  such that  2c+1  is also a Carmichael number, are also not found be me.  Do they exist ?

Q2. Redo Q1 but looking for c & 2c-1 Carmichaels.

A002997 & b-file

Emmanuel Vantieghem wrote (March 1, 2012):

If  c  is a Carmichael number of the form  4m+3  and  c = 2n+1, then  n  cannot be a squarefree number with three prime factors.

Proof :

Let  n = p q r  be a number with three different odd prime divisors  p, q, r.

Assume  c = 2 n + 1  is a Carmichael number.  Then, c must be a product of at least three different prime factors  P(1), P(2), ... , P(h) and  P(i) - 1 |  c - 1 = 2 p q r  for all  i = 1, 2, ... ,h.  Thus,  P(i)  must be one of the following numbers

        3, 2p+1, 2q+1, 2r+1, 2qr+1, 2pr+1, 2pq+1, 2pqr+1

All these numbers are of the form  4m+3.  Since  c  is also of the form  4m+3, we must have : h is odd.  So, h = 3, 5  or  7.  We can drop the cases  h = 5, 7  (the product of the P(i) would be strictly bigger than  2n+1).  Thus, h = 3, and we have following possibilities :

1) 2n+1 = 3(2p+1)(2q+1).

This would imply :  p q r = 6 p q + 3 p + 3 q + 1, whence  p q r > 6 p q.

Since  2n+1  is divisible by 3, n is not and thus : p, q, r  are strictly bigger than 3,  which implies  p q r =< 8 p q.  Hence : r must be 7.  We thus are left with  p q = 3 p + 3 q + 1, which is easily seen to be impossible.

(similar cases are  2n+1 = 3(2p+1)(2r+1) or 3(2q+1)(2r+1) ).

2) 2n+1 = 3(2p+1)(2pq+1)

This would imply : p q r = 6 q p^2 + 3 p q + 3 p + 1.  This gives, modulo  p q :

0 = 3 p + 1 (mod p q ).      (*)

From 3 < q  it follows  3 p < p q  and hence 3 p + 1 <= p q.  But equality is not possible, hence  3 p + 1 < p q.  This makes the congruence (*) impossible.

Similar cases are : 2c+1 = 3(2p+1)(2pr+1), 3(2q+1)(2pq+1), 3(2q+1)(2qr+1), etc ...

3) 2n+1 = 3(2p+1)(2qr+1) and 'similar cases' are not possible.  The right hand member is too big. The same holds for the case  2n+1 = 3(2pr+1)(2pq+1)  and similar cases and for the case in which 2n+1 is not divisible by 3.

This ends the proof of our statement.

As a consequence we find that no Carmichael number  n  with three prime factors has the property that  2n+1  is also a Carmichael number.


This argumentation cannot completely solve the 2c+1 problem since there exists a product of four different primes  p q r s  such that  2 p q r s + 1  is a Carmichael number.

As a matter of fact, using the tables of Richard Pinch ( I could find two such numbers :

n = 13*43*41081*6750684637, 2n+1 = 310049210890163447, a Carmichael number 

n = 3*19*121631*59176737797, 2n+1 =820540740628507399, also a Carmichael number.

There are no smaller examples.

(Remark that  n  is not Carmichael in both examples)


There is no similar way out for the  2c - 1  problem.  However, the use of Pinch's tables enabled me to figure out that 2^(2c-2)  is incongruent  1  modulo  2c-1 for all Carmichael numbers  c < 10^18, for which  2c-1  is not prime

I also examined that congruence for some bigger Carmichael numbers, and at present I found no counterexample.

If we would try to attack the  2c+1  problem in this way, we found that  2^(2c)  is incongruent 1 modulo 2c+1  for all Carmichael numbers less than 10^18 for which  2c+1  is not prime, except one : c = 9890881,  for which we found out that  5^(2c)  is incongruent modulo 2c+1.


On March 3, 2012 Richard Pinch wrote:

I had a look at problem 57 and can report that there are no examples of (C,2C+1) both being Carmichael numbers when C is less than 10^21... I can report the same for pairs (C,2C-1).


Records   |  Conjectures  |  Problems  |  Puzzles