Search a number
k-Lehmer numbers
A number  $n$  is a  $k$-Lehmer number if  $\phi(n)$  divides  $(n-1)^k$.

Since  $\phi(p)=p-1$  when  $p$  is prime, all prime numbers are  $1$-Lehmer numbers.

Every number which is  $k$-Lehmer is also  $(k+1)$-Lehmer, and thus for simplicity I will call a number  $k$-Lehmer only if it is not  $(k-1)$-Lehmer, and I will consider only composite Lehmer numbers.

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.

The following table reports the smallest  $k$-Lehmer number for  $k$  from 2 to 36.

2561   9771   16494211   2316711935   308053383171
315 1043435 17196611 24126027651 314294967295
4451 113855 182089011 2550529027 3232212942851
551 1231611 19983055 26756493591 3390665917447
6679 1313107 208061051 27252645135 34129352336131
7255 14272163 213342387 284446487299 35362186539779
82091 1565535 2231580931 29858993459 36972094264435

Grau & Antonio M. Oller-Marcén have proved several results. For example, that every Carmichael number is also a  $k$-Lehmer number.

The first  $k$-Lehmer numbers 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 more terms

You can download a zipped text file (kLehmer_up_1e12.zip) (length = 9.3 MB), containing the 2103055  $k$-Lehmer numbers up to  $10^{12}$.

Pictorial representation of remainders (mod 2, 3, ...,11) frequency. For a table of values and more details click here
remainders of K-Lehmer numbers

A graph displaying how many K-Lehmer numbers are multiples of the primes p from 2 to 71. In black the ideal line 1/p.
divisibility of K-Lehmer numbers
Useful links OEIS, Sequence A187731
José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, Integers, 12(2012), #A37.
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions International Journal of Number Theory 9 (2013), 1215-1224.
Mathworld, Lehmer's Totient Problem
K-Lehmer numbers can also be... (you may click on names or numbers and on + to get more values)

aban 15 51 85 + 998432000161 alternating 85 561 703 + 989438341 amenable 85 133 481 + 999962185 apocalyptic 247 1105 1141 + 29341 arithmetic 15 51 85 + 9997351 astonishing 15 78403 Bell 15 binomial 15 91 435 + 999406030321 brilliant 15 247 451 + 998849281 c.decagonal 451 2761 5611 + 998291946961 c.heptagonal 4411 5461 19951 + 839844151147 c.nonagonal 91 595 703 + 999406030321 c.pentagonal 51 1891 23281 + 981056721331 c.square 85 481 1105 + 964634109181 c.triangular 85 1891 26335 + 501279470749 cake 15 1351 3658901 29269801 canyon 435 703 949 + 9876102367 Carmichael 561 1105 1729 + 999629786233 congruent 15 85 133 + 9997351 constructible 15 51 85 + 4294967295 Cunningham 15 255 511 + 945192284101 Curzon 561 2465 8481 + 184504881 cyclic 15 51 85 + 9997351 D-number 15 51 771 196611 d-powerful 2465 3145 8245 + 9828295 de Polignac 2465 10963 14611 + 99815821 decagonal 85 451 1105 + 999890502997 deceptive 91 259 451 + 99976607641 deficient 15 51 85 + 9997351 dig.balanced 15 595 2701 + 199803151 double fact. 15 Duffinian 85 133 247 + 9996205 economical 15 133 259 + 19981237 emirpimes 15 51 85 + 99947761 equidigital 15 133 259 + 19981237 eRAP 32740580041 49497717361 396432377719 928645234777 esthetic 212323 Eulerian 247 evil 15 51 85 + 999962185 Friedman 1285 2509 21845 + 597871 gapful 451 561 1111 + 99994249447 happy 91 133 763 + 9969961 Harshad 133 247 481 + 9996982621 heptagonal 3367 4141 9211 + 999573669121 hex 91 1141 1261 + 980322013567 hexagonal 15 91 435 + 999406030321 hoax 85 1111 4369 + 99264451 Hogben 91 133 703 + 984588837961 house 1285 hyperperfect 250321 iban 247 703 771 + 771001 idoneal 15 85 133 inconsummate 771 3855 8481 + 983055 interprime 15 771 1695 + 99961681 Jacobsthal 85 5461 21845 + 91625968981 junction 511 1417 1615 + 99948451 Kaprekar 703 670033 katadrome 51 85 91 763 Lucas 167761 lucky 15 51 133 + 9973693 Lynch-Bell 15 magic 15 1105 1695 + 910382081071 magnanimous 85 2465 6601 88621 metadrome 15 247 259 + 12346789 modest 133 511 763 + 1948016071 Moran 133 247 481 + 98205733 Motzkin 51 mountain 451 481 561 + 13467987541 nialpdrome 51 85 91 + 87777776521 nonagonal 69231 211191 550639 + 997375675591 nude 15 1111 11155 + 771715 oban 15 85 511 + 763 octagonal 133 481 2465 + 999918240133 odious 91 133 247 + 999903451 palindromic 595 949 1111 + 153452254351 pancake 5461 7141 17767 + 792767765791 panconsummate 15 85 91 + 3097 pandigital 15 16405 39865 + 14821261 partition 15 pentagonal 51 247 5551 + 999932033707 pernicious 91 133 247 + 9995189 Perrin 51 persistent 14062987315 14350972681 14352078469 + 98367501241 plaindrome 15 133 247 + 2478889999 Poulet 561 1105 1387 + 999986341201 Proth 481 1729 4033 + 888547573761 repdigit 1111 repunit 15 85 91 + 984588837961 Rhonda 534391 683116554121 Ruth-Aaron 15 949 20451 + 991675627501 self 255 435 703 + 999271663 semiprime 15 51 85 + 99947761 sliding 133 Smith 85 1111 4369 + 99264451 sphenic 255 435 561 + 99991111 star 1261 7141 14701 + 896360752261 straight-line 1111 strobogrammatic 1111 101101 subfactorial 14833 super-d 247 481 511 + 9996205 taxicab 1729 39639691 788964463 + 850910580037 tetrahedral 9139 1004731 10507399 + 871058910085 tetranacci 15 triangular 15 91 435 + 999406030321 trimorphic 51 uban 15 51 85 + 21025000099 Ulam 451 949 1387 + 9935131 undulating 595 949 4141 + 61616161 unprimeable 3145 7735 9265 + 9946615 upside-down 91 72583 12346789 99991111 vampire 81992911 1508692531 4869114151 + 5763104941 wasteful 51 85 91 + 9997351 Woodall 2047 Zeisel 1729 294409 7355671 + 856666552249 Zuckerman 15 1111 zygodrome 1111 4411 11155 + 887755665511