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$.

  • $\begingroup$ Note: $53$ is a factor of $n = 2433601 = 17\times 37 \times 53 \times 73\; $ which is a Carmichael number by Korselt's criterion. $\endgroup$ – gammatester Jul 30 '14 at 8:52
  • 1
    $\begingroup$ 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 $\endgroup$ – gammatester Jul 30 '14 at 9:21
  • $\begingroup$ 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) $\endgroup$ – Dane Bouchie Jul 30 '14 at 19:55
  • $\begingroup$ A Carmichael-number $N$ divisible by $p$ must satisfy the congruence $N\equiv p\ (\ mod\ p(p-1)\ )$ $\endgroup$ – Peter Oct 29 '15 at 16:52
  • $\begingroup$ What is the largest number in the lists ? $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.