Lehmer Numbers

The number 26599 is, amongst other things, a 3-Lehmer number which means that:$$\phi(26599)|(26599-1)^3$$In other words, the totient of the number divides the number less one raised to the third power. So let's generalise this statement and say that a number \(n\) is a \(k\)-Lehmer number if:$$\phi(n)|(n-1)^k$$However, the totient of a prime number \(p\) is \( (p-1) \) and so clearly all prime numbers could be regarded as Lehmer numbers and so prime numbers are excluded and only composite numbers considered.

Another point is that every \(k\)-Lehmer number is also \((k+1)\)-Lehmer and so it makes sense to impose the condition that, for a number to be considered \(k\)-Lehmer, it should not be \((k-1)\)-Lehmer. That being said let's consider 1-Lehmer numbers or numbers such that: $$\phi(n)|(n-1)$$Well, clearly all prime numbers satisfy this condition but we have excluded them and are considering only composite numbers. Are there any composite numbers that satisfy the condition? We don't know. To quote from Numbers Aplenty:

The existence of a composite 1-Lehmer number (usually simply called Lehmer number) is still an open problem and several results have been proved about these numbers (which probably do not exist). For example, Cohen and Hagis have proved that such a number, if it exists, must be greater than \(10^{20}\) and be the product of at least 14 primes.

So that takes us to 2-Lehmer numbers or numbers such that:$$\phi(n)|(n-1)^2$$There are only 36 of these in the range up to one million with 561 being the smallest. They are (permalink):

561, 1105, 1729, 2465, 6601, 8481, 12801, 15841, 16705, 19345, 22321, 30889, 41041, 46657, 50881, 52633, 71905, 75361, 88561, 93961, 115921, 126673, 162401, 172081, 193249, 247105, 334153, 340561, 378561, 449065, 460801, 574561, 656601, 658801, 670033, 930385

The 3-Lehmer numbers or numbers such that:$$\phi(n)|(n-1)^3$$are more numerous and in the range up to 40,000 there are 63 with 15 being the smallest. They are (permalink):

15, 85, 91, 133, 247, 259, 481, 703, 949, 1111, 1891, 2071, 2701, 2821, 3097, 3145, 3277, 4033, 4141, 4369, 4681, 5461, 5611, 5713, 6031, 7081, 7957, 8911, 9211, 9265, 10585, 11041, 11305, 12403, 13333, 13741, 13981, 14089, 14701, 14833, 15181, 16021, 16441, 16745, 17767, 18721, 22261, 23001, 24661, 25351, 26599, 27331, 29341, 31417, 31609, 31621, 34861, 35371, 35881, 36661, 37969, 38503, 39865

Numbers Aplenty has a table of the smallest numbers for values of \(k\) from 2 to 36. See Figure 1.

Figure 1

 Up to 40,000, the Lehmer numbers, for all values of \(k\) are:

15, 51, 85, 91, 133, 247, 255, 259, 435, 451, 481, 511, 561, 595, 679, 703, 763, 771, 949, 1105, 1111, 1141, 1261, 1285, 1351, 1387, 1417, 1615, 1695, 1729, 1843, 1891, 2047, 2071, 2091, 2119, 2431, 2465, 2509, 2701, 2761, 2821, 2955, 3031, 3097, 3145, 3277, 3367, 3409, 3589, 3655, 3667, 3855, 4033, 4039, 4141, 4369, 4411, 4681, 4795, 4921, 5083, 5151, 5383, 5461, 5551, 5611, 5629, 5713, 6031, 6205, 6331, 6601, 6643, 6735, 7051, 7081, 7141, 7471, 7501, 7735, 7957, 8071, 8119, 8227, 8245, 8401, 8481, 8695, 8827, 8911, 8995, 9061, 9079, 9139, 9211, 9253, 9265, 9367, 9605, 9709, 9919, 9997, 10213, 10291, 10573, 10585, 10795, 10963, 11041, 11155, 11305, 11899, 12403, 12801, 12901, 13021, 13107, 13333, 13651, 13741, 13747, 13855, 13981, 14089, 14491, 14497, 14611, 14701, 14833, 14911, 14989, 15051, 15181, 15211, 15811, 15841, 16021, 16297, 16405, 16441, 16471, 16531, 16705, 16745, 16771, 16861, 17563, 17611, 17733, 17767, 18019, 18031, 18151, 18631, 18721, 18745, 18907, 18967, 19345, 19669, 19951, 20419, 20451, 20595, 20995, 21037, 21349, 21679, 21845, 21907, 21931, 22015, 22261, 22321, 22359, 23001, 23281, 23959, 24199, 24415, 24643, 24661, 24727, 24871, 25123, 25141, 25351, 25669, 26281, 26335, 26467, 26599, 26923, 27223, 27331, 27511, 27721, 28231, 28453, 28645, 28939, 29341, 30481, 30583, 30889, 31171, 31417, 31459, 31609, 31611, 31621, 32215, 32407, 32551, 32691, 33001, 33709, 34441, 34861, 35113, 35371, 35551, 35881, 36091, 36391, 36499, 36661, 36751, 36805, 37231, 37921, 37969, 38165, 38503, 39091, 39403, 39491, 39817, 39831, 39865

Looking at this list, it can be seen that the Lehmer number previous to 26599 was 26467 while the next one is 26923. 26599 was my diurnal age yesterday and so it will more than a year before I see another one. One last point is that every Carmichael number is also a \(k\)-Lehmer number. This post is fairly superficial and I'm sure that a lot more can be said about Lehmer numbers but my purpose here is just to introduce them because I hadn't made a dedicated post about these numbers since beginning this blog.

There may be a link between pseudoprimes and Lehmer numbers that would be interesting to explore.

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.