Carmichael Numbers

Before discussing Carmichael numbers, the prelude to my interest in these numbers must be described. On the 29th January 2019, I turned 25503 days old. As always, I started my morning by investigating the mathematical properties of this number, looking firstly for relevant entries in the Online Encyclopaedia of Integer Sequences or OEIS. Nothing much of interest showed up so I moved on to Numbers Aplenty where mention was made that it's a D-number.

The description for a \(D\)-number was:

Also known as \(3\)-Knödel numbers, they are numbers \(n>3\) such that \(n\) divides \(k^{n-2}-k\) for all \(1<k<n\) relatively prime to \(n\). For example, \(9\) is a D-number since it divides all the numbers  \(2^7-2\),  \(4^7-4\), \(5^7-5\), \(7^7-7\) and \(8^7-8\).

D-numbers are listed in the OEIS (A033553) but 25503 does not show up in a search because it's too far down the list of numbers. Only the following numbers are displayed:

9, 15, 21, 33, 39, 51, 57, 63, 69, 87, 93, 111, 123, 129, 141, 159, 177, 183, 195, 201, 213, 219, 237, 249, 267, 291, 303, 309, 315, 321, 327, 339, 381, 393, 399, 411, 417, 447, 453, 471, 489, 501, 519, 537, 543, 573, 579, 591, 597, 633, 669, 681, 687, 693, 699, 717, 723, 753, 771, 789, 807, 813, 819

All of these numbers are odd and composite, with most being divisible by 3. The first term that isn't divisible by 3 is 50963, the 2000\(^{th}\) term. 25503 is the 1092\(^{nd}\) term with neighbours 25401 and 25539.

Just to confuse matters, there are two ways of expressing the condition for a number to be a \(D\)-number or \(3\)-Knödel number. This is because:$$ \frac{k^{n-2}-k}{n}=k \times \frac{k^{n-3}-1}{n} $$We know that \(k\) and \(n\) are coprime, so \(n\) must divide \( k^{n-3}-1 \). This means that:$$\begin{align}
k^{n-3}-1&\equiv 0 \pmod{n} \\
k^{n-3} &\equiv 1 \pmod{n}

\end{align} $$Thus the 3 in the \(3\)-Knödel designation comes from the \(n-3\) index to the \(k\) base and the generalisation follows that a \(n\)-Knödel number for a given positive integer \(n\) is a composite number \(m\) with the property that each \(k < m\) coprime to \(m\) satisfies \( k^{m-n} \equiv 1 \pmod {m}\). The concept is named after Walter Knödel. The set of all \(n\)-Knödel numbers is denoted \(K_n\). The special case \(K_1\) represents the Carmichael numbers.

As can be seen by the initial values in Figure 1, the Carmichael numbers are few and far between:

Figure 1: source 

The Carmichael numbers lead us on to Fermat's Little Theorem which states that if \(p\) is a prime number and \(a\) is a natural number then:$$a^{\,p-1}-1 \equiv 0 \pmod{p} $$There is a proof of this theorem by mathematical induction on WolframMathWorld and the theorem shows that:

if p is prime, there does not exist a base \(a<p\) with \(a\) and \(p\) coprime such that \(a^{\,p-1}-1\) possesses a nonzero residue modulo \(p\). If such base \(a\) exists, \(p\) is therefore guaranteed to be composite. However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that \(p\) is prime. The property of unambiguously certifying composite numbers while passing some primes make Fermat's little theorem a compositeness test which is sometimes called the Fermat compositeness test. A number satisfying Fermat's little theorem for some nontrivial base and which is not known to be composite is called a probable prime. Composite numbers known as Fermat pseudoprimes (or sometimes simply "pseudoprimes") have zero residue for some values of \(a\) and so are not identified as composite. Worse still, there exist numbers known as Carmichael numbers (the smallest of which is 561) which give zero residue for any choice of the base \(a\) relatively prime to \(p\). 

This brings us full circle and though much more could be said, at least I have a firmer grasp of what Carmichael numbers are all about. I have written about Fermat pseudoprimes in an earlier post on Thursday, 30 August 2018. I also make reference to the Carmichael numbers in that post, noting that these numbers have at least three prime factors e.g. 561 = 3 x 11 x 17.

Before finishing up, I should refer to the OEIS A002997 entry for the Carmichael numbers. These are the numbers listed there (note that the majority end in the digit 1):

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461  

ADDENDUM (added September 7th 2021):

A225509

-5-Knödel numbers.

15, 55, 75, 91, 175, 247, 275, 715, 775, 1275, 1435, 2275, 2635, 3075, 3355, 4615, 6355, 6475, 7975, 8827, 9139, 10075, 10675, 11275, 11935, 13515, 14555, 21775, 26455, 28975, 30415, 31675, 32395, 43615, 46075, 47275, 52195, 59755, 64255, 77275, 78403, 81055

An interesting extension of \(n\)-Knödel numbers to \(n\) negative, in this case \(n= -5\). Composite numbers \(m > 0\) such that if \(1 < a < m\) and gcd(\(m,a\)) = 1 then \(a^{\,m+5} \equiv 1 \pmod {m}\). Permalink.