Don't take life too seriously: it's just a temporary situation

k-Lehmer (numeri di)

Teoria dei numeri 

Un numero composto n è detto “numero di k-Lehmer” se φ(n) divide (n – 1)k. I numeri primi sono esclusi perché se n è primo, φ(n) = n – 1.

 

Esistono numeri di k-Lehmer per qualsiasi valore di k maggiore di 1; secondo una congettura di Lehmer però non ne esistono per k = 1. Dalla definizione segue che se n è un numero di k-Lehmer, è anche un numero di k-Lehmer per mk.

 

I numeri di 1-Lehmer sono chiamati semplicemente “numeri di Lehmer”.

 

Se tutti i primi che dividono φ(n) dividono anche n – 1, n è un numero di k-Lehmer per qualche valore di k. Di conseguenza tutti i numeri di Carmichael sono numeri di k-Lehmer per qualche valore di k.

 

Dato che φ(n) è pari per n > 2, i numeri di k-Lehmer sono tutti dispari; inoltre per un numero di k-Lehmer n vale MCD(n, φ(n)) = 1, quindi i numeri di k-Lehmer non sono multipli di quadrati.

 

La tabella seguente mostra i minimi numeri di Carmichael che sono numeri di k-Lehmer, ma non sono numeri di k-Lehmer per valori inferiori di k (José María Grau, The Online Encyclopedia of Integer Sequences http://oeis.org).

k

Minimo numero di Carmichael

2

561

3

2821

4

838201

5

41471521

6

45496270561

7

776388344641

8

344361421401361

9

375097930710820681

10

330019822807208371201

 

Tranne 561, fissato k il minimo numero di Carmichael che sia un numero di k-Lehmer ha esattamente k fattori primi distinti per k fino a 10, ma non è stato dimostrato che questa proprietà debba valere sempre.

 

La tabella seguente mostra il minimo numero di k-Lehmer, che non sia tale per valori inferiori di k per k fino a 30 (M. Fiorentini, 2013).

k

Minimo numero di k-Lehmer

2

561

3

15

4

451

5

51

6

679

7

255

8

2091

9

771

10

43435

11

3855

12

31611

13

13107

14

272163

15

65535

16

494211

17

196611

18

2089011

19

983055

20

8061051

21

3342387

22

31580931

23

16711935

24

126027651

25

50529027

26

756493591

 27

252645135

28

4446487299

29

858993459

30

8053383171

 

Nel 2012 José María Grau e Antonio M. Ollen-Marcén, 2012 dimostrarono alcune proprietà dei numeri di k-Lehmer:

  • dati due primi dispari distinti p = 2adα + 1 e q = 2bdβ + 1, con d, α e β dispari e α e β primi tra loro, allora n = pq è un numero k-Lehmer per k > 1 se e solo se a + bka e αβ divide dk − 2; in particolare nessun prodotto di 2 primi è un numero di 2-Lehmer;

  • dati due primi p = 2n3 + 1 e q = 2m3 + 1, se m > n e mn è dispari, pq è un numero di k-Lehmer per k tale che knm + n;

  • se n è un numero di k-Lehmer e Congruenza che un numero di k-Lehmer deve soddisfare per essere uno pseudoprimo di Fermat per un intero a primo rispetto a n, n è pseudoprimo di Fermat in base b;

  • un numero della forma Formula per numeri di Carmichael che sono anche numeri di n-Lehmer, con k multiplo di 2n – 4 ma non potenza di 2, n maggiore di 3 e gli n fattori del prodotto tutti primi, è un numeri di Carmichael e un numero di n-Lehmer, ma non di (n – 1)-Lehmer.

 

Nathan McNew considerando il numero totale dei numeri k-Lehmer minori di n per tutti i valori di k dimostrò nel 2012 che:

  • quelli con d fattori primi per d > 1 non superano Limite superiore per i numeri di k-Lehmer minori di n con d fattori primi;

  • quelli con 2 fattori primi per k > 1 asintoticamente tendono a un limite non superiore a Limite superiore asintotico per i numeri di k-Lehmer minori di n con 2 fattori primi;

  • il numero totale, comprendendo però anche i numeri primi, tende a un limite non superiore a Limite superiore asintotico per i numeri di k-Lehmer minori di n, includendo i numeri primi, che è lo stesso limite dei numeri di Carmichael ed è una sovrastima nei due casi.

Lo stesso matematico dimostrò anche che i numeri di k-Lehmer non superiori a n sono meno di Limite superiore per i numeri di k-Lehmer minori di n.

 

La tabella seguente mostra il numero di numeri di k-Lehmer minori di 10n, per n sino a 11 (Nathan McNew, 2012).

k

Numeri di k-Lehmer minori di 10n

1

0

2

4

3

19

4

103

5

422

6

1559

7

5645

8

19329

9

64040

10

205355

11

631949

 

La tabella seguente mostra i numeri di k-Lehmer fino a 10000. Per ogni valore di k sono riportati solo i numeri che non sono numeri di k-Lehmer per valori inferiori di k.

k

Numeri di k-Lehmer

2

561, 1105, 1729, 2465, 6601, 8481

3

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

4

451, 511, 763, 1261, 1387, 1417, 2047, 2509, 2761, 3589, 5629, 7141, 7501, 8401, 9253

5

51, 435, 1141, 1285, 2119, 2955, 3031, 3367, 4411, 4921, 5551, 6205, 7471, 8227, 8695, 9061, 9079, 9139, 9605, 9709, 9919, 9997

6

679, 1843, 3409, 4795, 6331, 6643, 8119, 8245

7

255, 595, 1351, 1615, 1695, 2431, 3655, 3667, 4039, 5083, 5151, 9367

8

2091, 7051, 8071, 8827

9

771, 5383, 6735, 7735

11

3855, 8995

 

Qui trovate i numeri di k-Lehmer fino a 109, ciascuno seguito dal minimo valore di k per il quale valga la proprietà (M. Fiorentini 2013).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.