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.