# Are there any primes that are never a factor of a Carmichael number?

Is there a prime number $p$ that $p > 2$, and in which $p$ is a never a factor of any Carmichael number $C_n$:

(p ∤ $C_n$)

After a quick glance at some Carmichael number factors, $p$ must be greater or equal to $53$.

• Note: $53$ is a factor of $n = 2433601 = 17\times 37 \times 53 \times 73\;$ which is a Carmichael number by Korselt's criterion. – gammatester Jul 30 '14 at 8:52
• The first prime that does not appear on the list in de.wikibooks.org/wiki/… seems to be 167. Meanwhile I found a lists with more entries numericana.com/data/crump.htm and numericana.com/data/korselt.htm – gammatester Jul 30 '14 at 9:21
• Thanks for those lists. So since $p$ must now be greater than $10000$, this is headed toward looking false. (However, there still might be a prime) – Dane Bouchie Jul 30 '14 at 19:55
• A Carmichael-number $N$ divisible by $p$ must satisfy the congruence $N\equiv p\ (\ mod\ p(p-1)\ )$ – Peter Oct 29 '15 at 16:52
• What is the largest number in the lists ? – Peter Oct 29 '15 at 20:48

The answer to your question should be no. Every odd prime $p$ is a factor of infinitely many Carmichael numbers. To see this let $N$ be a Carmichael number, and $p$ $|$ $N$ with $p$ prime. $p-1$ $|$ $N-1$ is true, then all other prime factors $p_2$, $p_3$.... $p_n$, ($p_2$ * $p_3$*....$p_n$) $=$ $1$ $\pmod {p-1}$. http://www.numericana.com/data/crump.htm says that $\phi(n)$ must be relatively prime to $n$ to be a divisor of a Carmichael number, for when $n$ is prime $\phi(n)$ is $n-1$ and two consecutive integers are coprime. However, some numbers such as $21$, $39$, $55$, and $57$ cannot be divisors of Carmichael numbers. Korselt's criterion defines a Carmichael number $N$ a square free integer such that all primes $p$ $|$ $n$, $p-1$ $|$ $n-1$. Here are simply why these numbers are never divisors of Carmichael Numbers:

Suppose $N$ is a Carmichael Number:

$N$ $|$ $21$ $=$ $3*7$, $N-1$ $|$ $2$, $N-1$ $|$ $2*3$. $N$ $|$ $3$ on the other hand, we also have $N-1$ $|$ $3$, a contradiction since no two consecuative integers are both divisible by a number $>$ $1$.

as for these cases too:

$N$ $|$ $39$ $=$ $3*13$

$N$ $|$ $55$ $=$ $5*11$

$N$ $|$ $57$ $=$ $3*19$

More simply for that two primes $p$ and $pk+1$, a Carmichael number is never a multiple of $p$($pk+1$).

I hope this helps with some of the understanding of divisors of Carmichael Numbers.

• This post only has a proof that some pairs of primes are not factors of a Carmichael number. – Armadillo Jim Jan 27 '17 at 21:32