2015 is a so called Lucas-Carmichael number. I believe (for reasons that I will explain below) that the 'Carmichael' in the name is a reference to ordinary Carmichael numbers and not to the person Carmichael. (When ignoring that the Carmichael numbers are of course named after the person Carmichael.) So the question arises how 'Lucas' entered the name, especially since he was dead for some years when Carmichael numbers (let alone Lucas-Carmichael numbers) were defined. Does anybody know when Lucas-Carmichael numbers were so named and why?

Background: Carmichael numbers

From Fermat's little theorem one can cook up a nice test to see if a number $n$ is prime: choose a number $a$ and see if $n$ divides $a^n - a$. If the test says 'no', then the answer [to the question 'is $n$ prime?'] is 'no' as well. If the test says 'yes' then, hmm, we don't really know what the real answer is. We have some more faith that $n$ might be prime, but to be more certain we better try some other value of $a$. Now this naturally leads to the question: are there numbers $n$ such that $n$ divides $a^n - a$ for every $a$ coprime to $n$ but with $n$ nevertheless not prime. Needless to say it would be really annoying if such numbers exist.

Unfortunately they do: Carmichael found the first example (561 = 3 * 11 * 17) in 1910 (according to Wikipedia). In 1994 it was even proved that there are infinitely many.

More background: Korset's criterion

Some ten years before any Carmichael number was known, Korset proved (perhaps in an attempt to rule out their existence?) that a number $n$ is a Carmichael number if and only if $n$ is square free and

$$p-1|n-1 \textrm{ whenever } p|n$$ with $p$ prime.

Now this doesn't do much to improve the usefulness of the Fermat primality test, since finding all prime factors of $n$ is, trivially, at least as hard as testing whether $n$ is prime, but it is still a very nice result.

Lucas-Carmichael numbers

Lucas-Carmichael numbers are defined as squarefree numbers $n$ satisfying

$$p+1|n+1 \textrm{ whenever } p|n$$ with $p$ prime.

(E.g. 2015 = 5*13*31 and 2016 = 6*336 = 14*144 = 32*63)

So it looks very much like they were invented when someone thought 'hey, let's see what happens if we replace all the minuses in Korset's criterion by pluses!' This is a legitimate thing to do in situations like this, as is naming the resulting numbers after the Carmichael numbers they were (seemingly) inspired by.

Only I would opt for something like 'topsy-turvy Carmichael numbers', 'Ultra-positive Carmichael numbers', 'anti-Carmichael numbers' or something along these lines. In other words, the question remains:

What do Lucas-Carmichael numbers have to do with Lucas?

  • $\begingroup$ Update: it has become clear to me that when thinking about Lucas I was actually thinking about Mersenne and that the actual Lucas lived in the 19th century. So I changed 'dead for some centuries' above to 'dead for some years'. Question still remains the same. $\endgroup$ – Vincent Dec 31 '14 at 18:35
  • 1
    $\begingroup$ I haven't understood or verified it, but according to mersenneforum.org/showthread.php?t=3359, a Lucas–Carmichael number "is a Lucas pseudoprime to all Lucas sequences". There are also other definitions of Carmichael–Lucas numbers in the literature, so I don't think this terminology is very solid. $\endgroup$ – ShreevatsaR Mar 18 '16 at 20:02
  • 1
    $\begingroup$ Lucas did a fair bit of work with trying to understand how to factor or test the primality of n given information about n+1. In contrast, most prior work involved understanding n-1. This may be where the word choice is coming from. . $\endgroup$ – JoshuaZ Aug 30 '18 at 0:10

The earliest primality tests were based on Fermat's Little Theorem, according to which $a^{p-1} \equiv 1 \bmod p$ for primes $p \nmid a$, which deals with the multiplicative group of the finite field with $p$ elements. Later, Lucas discovered tests that were based on what we know as a natural subgroup of order $p+1$ inside the multiplicative group of order $p^2-1$ in the finite field with $p^2$ elements. This justifies naming objects you get by replacing elements of order dividing $p-1$ by elements whose order divides $p+1$ after Lucas, even though he did not have to do anything with the objects in question, in this case Carmichael numbers.

The first Carmichael numbers, by the way, were found long before Korselt found his criterion by the Czech priest Vaclav Simerka in 1885; see my article here.


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.