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

Pseudoprimi di Somer – Lucas

Teoria dei numeri 

Data una successione di Lucas generalizzata con parametri P e Q, se n e Q sono primi tra loro, infiniti elementi della sequenza sono multipli di n. Se n è primo e non divide Q, il minimo indice k per il quale Uk ≡ 0 mod n, è un divisore di n – (D | n), dove D = P2 – 4QSimbolo di Jacobi (D | n) qui e nel seguito indica il simbolo di Jacobi; gli pseudoprimi di Somer – Lucas rispetto a P e Q sono i numeri composti dispari, primi rispetto a D, con la stessa proprietà.

 

Dato che per ogni sequenza di Lucas generalizzata U2m(P, Q) = –U2m(–P, Q) e U2m + 1(P, Q) = U2m + 1(–P, Q), se n è pseudoprimo di Somer – Lucas rispetto a P e Q, lo è anche rispetto a –P e Q.

 

Un parametro importante è il quoziente d = (n – (D | n)) / k.

 

Lawrence Somer dimostrò nel 1996 che per ogni valore di d non multiplo di 4 gli pseudoprimi di Somer – Lucas sono in numero finito, che non ne esistono per d = 1 e trovò tutti quelli esistenti per d = 2, 3, 5 e 6.

 

Nel 1998 Walter Carlip, E. Jacobson e Lawrence. Somer dimostrarono che se la massima potenza di 2 che divide d è 2r, gli pseudoprimi di Somer – Lucas con almeno r + 2 divisori sono in numero finito.

 

Nel 2005 Walter Carlip e Lawrence Somer dimostrarono che:

  • un intero composto Scomposizione di n come prodotto di fattori primi è pseudoprimo di Somer – Lucas rispetto a P e Q se e solo se (n – (D | n)) / d divide Minimo comune multiplo, calcolato su tutti i fattori primi p(k) di n, di p(k)^(e(k) – 1)*(p(k) – (D | (p(k))), dove il minimo comune multiplo va calcolato su tutti i primi che dividono nMassimo comun divisore di n, di (n – (D | n)) / d, p(k) – (D | (p(k)), per tutti i primi pk che dividono n;

  • se n è pseudoprimo di Somer – Lucas, Diseguaglianza soddisfatta dagli pseudoprimi di Somer – Lucas;

  • se n = ab con a e b maggiori di 2 e primi tra loro e Scomposizione di a come prodotto di fattori primi, Diseguaglianza soddisfatta da n;

  • se n è uno pseudoprimo di Somer – Lucas, ω(n) ≥ log(d + 1) / log(3 / 2) – 1;

  • se n è uno pseudoprimo di Somer – Lucas e ω(n) < log(2 / 3)(2 * d), n non è multiplo di quadrati;

  • se n è uno pseudoprimo di Somer – Lucas, p(k)^(e(k) – 1) < 2 * (2 / 3)^ω(n) * (d + 1), quindi n non è multiplo di quadrati se ω(n) è abbastanza grande;

  • per ogni valore di d gli pseudoprimi di Somer – Lucas multipli di quadrati sono in numero finito;

  • per ogni valore di d e m gli pseudoprimi di Somer – Lucas multipli di m sono in numero finito;

  • per ogni valore di d e m gli pseudoprimi di Somer – Lucas con esattamente m fattori primi sono in numero finito;

  • per ogni valore di d tutti gli pseudoprimi di Somer – Lucas tranne un numero finito di eccezioni sono numeri di Carmichael – Lucas.

 

Nel 2007 gli stessi due matematici dimostrarono che:

  • gli pseudoprimi di Somer – Lucas sono in numero finito per ogni d = 4m, con m dispari e non uguale a un quadrato;

  • per ogni valore di d gli pseudoprimi di Somer – Lucas uguali a potenze di primi sono meno di dlog(2d).

 

La tabella seguente mostra gli pseudoprimi di Somer – Lucas fino a 100 rispetto a P da 1 a 20 e Q da –20 a 20.

Pseudoprimo

(P, Q)

9

(1, –13), (1, –4), (1, 5), (1, 14), (2, –7), (2, 11), (4, –19), (4, –1), (4, 17), (5, –19), (5, –1), (5, 8), (5, 17), (7, –16), (7, 2), (7, 11), (7, 20), (8, –13), (8, 5), (9, –20), (9, –19), (9, –17), (9, –16), (9, –14), (9, –13), (9, –11), (9, –10), (9, –8), (9, –7), (9, –5), (9, –4), (9, –2), (9, –1), (9, 1), (9, 2), (9, 4), (9, 5), (9, 7), (9, 8), (9, 10), (9, 11), (9, 13), (9, 14), (9, 16), (9, 17), (9, 19), (9, 20), (10, –13), (11, –16), (11, –7), (11, 2), (11, 20), (13, –19), (13, –10), (13, –1), (13, 8), (13, 17), (14, –19), (14, –1), (14, 17), (16, –7), (16, 11), (17, –13), (17, –4), (17, 5), (17, 14), (18, –19), (18, –17), (18, –13), (18, –11), (18, –7), (18, –5), (18, –1), (18, 1), (18, 5), (18, 7), (18, 11), (18, 13), (18, 17), (18, 19), (19, –13), (19, –4), (19, 5), (19, 14), (20, –7), (20, 11)

15

(1, –7), (1, 8), (2, –13), (2, 17), (3, –8), (3, 7), (4, –7), (5, –19), (5, –16), (5, –4), (5, –1), (5, 11), (5, 14), (6, –17), (6, 13), (7, –13), (7, 2), (7, 17), (8, –13), (8, 17), (9, –17), (9, –2), (9, 13), (10, –19), (10, –1), (10, 11), (11, –7), (11, 8), (12, 7), (13, 2), (13, 17), (15, –19), (15, –17), (15, –16), (15, –14), (15, –13), (15, –11), (15, –8), (15, –7), (15, –4), (15, –2), (15, –1), (15, 1), (15, 2), (15, 4), (15, 7), (15, 8), (15, 11), (15, 13), (15, 14), (15, 16), (15, 17), (15, 19), (16, –7), (17, –13), (17, 2), (18, 7), (19, –7), (19, 8), (20, –19), (20, –1), (20, 11)

21

(1, –10), (1, 11), (2, –19), (3, –20), (3, 1), (4, –13), (5, –19), (5, 2), (6, –17), (7, –19), (7, –13), (7, –10), (7, 2), (7, 8), (7, 11), (8, 11), (9, –5), (9, 16), (10, –13), (11, –13), (11, 8), (12, –5), (13, –10), (13, 11), (14, –19), (14, –13), (14, 11), (15, –17), (15, 4), (16, –19), (17, –13), (17, 8), (18, 1), (19, 2), (20, 11)

25

(1, –12), (1, –8), (1, 1), (1, 13), (1, 17), (2, –7), (3, –16), (3, –8), (3, 17), (4, –17), (4, –9), (4, –3), (6, –13), (6, –7), (6, 11), (7, –17), (7, –13), (7, –1), (7, 8), (7, 12), (8, –11), (8, 7), (8, 13), (9, –19), (9, 2), (11, –18), (11, –4), (11, –2), (11, 7), (12, 19), (13, –6), (13, –3), (13, –2), (13, 19), (16, –19), (16, 3), (17, –18), (17, –12), (17, –11), (17, 7), (17, 13), (17, 14), (18, –17), (18, –13), (18, –1), (19, –14), (19, –13), (19, –7), (19, 11), (19, 12), (19, 18)

27

(1, –13), (1, 14), (4, –19), (5, –1), (7, –16), (7, 11), (8, 5), (11, –7), (11, 20), (13, –10), (13, 17), (14, 17), (16, –7), (17, –4), (19, 5), (20, 11)

33

(1, –16), (1, 17), (3, 10), (5, –4), (6, 7), (7, 8), (8, –1), (9, –20), (9, 13), (10, 17), (11, –19), (11, –13), (11, –10), (11, –7), (11, 5), (11, 14), (11, 20), (12, –5), (13, 2), (14, –1), (15, –14), (15, 19), (17, –4), (18, 19), (19, –1)

35

(1, –17), (1, –13), (1, –9), (1, 1), (1, 12), (1, 18), (2, –17), (2, –1), (2, 13), (3, –13), (3, –11), (4, –19), (4, 17), (5, –19), (5, –17), (5, –8), (5, –3), (5, 9), (5, 13), (5, 16), (5, 18), (6, –17), (6, –13), (6, 1), (7, –16), (7, –13), (7, –11), (7, –3), (7, –2), (7, –1), (7, 2), (7, 3), (7, 13), (7, 19), (8, –3), (8, 19), (9, –8), (9, 11), (10, 1), (10, 3), (10, 17), (11, –19), (11, –18), (11, –4), (11, 2), (11, 8), (11, 16), (11, 17), (12, –17), (12, –1), (12, 13), (13, –16), (13, –6), (13, –3), (13, –2), (13, 8), (13, 19), (14, –17), (14, –9), (14, 17), (15, –13), (15, –2), (15, 4), (15, 8), (15, 11), (16, –3), (16, 11), (17, –13), (17, –12), (17, –11), (17, 3), (17, 9), (18, –13), (18, –11), (19, –12), (19, –8), (19, –3), (19, 6), (19, 11), (20, –13), (20, 11)

39

(1, –19), (1, 20), (3, –2), (5, –7), (7, 5), (8, –7), (9, –5), (10, 11), (11, 2), (12, 7), (13, –16), (13, –10), (13, –4), (13, –1), (13, 14), (13, 17), (14, –19), (15, –11), (16, 11), (17, 8), (18, 19), (19, 5)

45

(5, –19), (5, –1), (7, 2), (8, –13), (9, –17), (9, –7), (9, –2), (9, 8), (9, 13), (11, –7), (13, 17), (16, –7), (17, –13), (18, –13), (18, 7), (18, 17), (20, 11)

49

(1, –16), (1, –4), (1, 1), (1, 6), (2, –15), (3, –20), (3, 5), (3, 13), (4, –15), (4, –11), (5, –12), (5, –8), (5, –2), (5, 3), (6, –13), (8, –17), (8, –11), (8, 5), (8, 15), (9, –17), (9, –4), (9, 16), (9, 19), (10, 1), (10, 17), (11, –13), (11, –9), (11, 6), (12, –1), (13, –15), (13, –9), (13, 10), (13, 11), (16, –19), (16, 5), (16, 11), (16, 17), (17, –18), (17, –5), (17, 19), (17, 20), (18, –19), (19, 6), (19, 9), (19, 10), (19, 18), (20, –1), (20, 17), (20, 19)

51

(3, 13), (5, –13), (6, 1), (7, –1), (8, –19), (9, –2), (10, –1), (11, –16), (13, 8), (15, 19), (17, –19), (17, –16), (17, –13), (17, –4), (17, –1), (17, 2), (17, 8), (19, 2)

55

(1, –18), (1, 1), (1, 12), (2, –17), (2, –7), (3, –2), (3, 14), (4, –13), (5, –8), (5, –4), (5, 3), (5, 12), (6, –19), (6, 1), (7, –17), (7, –6), (7, –3), (7, –2), (7, 9), (8, 3), (8, 9), (9, 13), (9, 16), (10, –7), (11, –19), (11, –18), (11, –17), (11, –13), (11, –8), (11, –7), (11, –2), (11, 1), (11, 3), (11, 12), (11, 16), (12, –7), (12, 17), (13, –17), (13, –7), (13, –6), (13, 2), (13, 4), (14, –19), (14, –13), (15, –17), (15, –14), (15, –13), (15, –2), (15, 19), (16, –19), (16, 1), (17, 3), (17, 7), (17, 14), (18, –17), (19, –13), (19, –12), (19, –8), (20, –17), (20, –9), (20, –7)

57

(3, –5), (5, –16), (7, –4), (10, –7), (13, –1), (15, –11), (17, 2), (19, –13), (19, –10), (19, 5), (19, 11), (19, 17), (19, 20)

63

(1, –4), (4, –1), (5, –19), (5, 17), (7, 2), (7, 11), (9, –19), (9, –16), (9, –11), (9, –5), (9, –4), (9, –2), (9, 2), (9, 5), (9, 10), (9, 16), (9, 17), (9, 19), (10, –13), (11, –16), (11, 20), (13, –10), (13, –1), (13, 17), (14, –19), (17, –13), (17, 5), (18, –13), (18, –1), (18, 1), (18, 5), (18, 13), (18, 19), (19, –4), (19, 5), (20, 11)

65

(1, –4), (1, 1), (3, –17), (4, 1), (5, 6), (5, 12), (5, 17), (5, 19), (7, –16), (7, –8), (7, –1), (8, –1), (9, 1), (9, 8), (9, 16), (10, –17), (10, 3), (10, 11), (11, –9), (11, –3), (11, 17), (12, –17), (12, 7), (13, –17), (13, –16), (13, –12), (13, –3), (13, –1), (13, 3), (13, 4), (13, 9), (13, 12), (13, 14), (13, 17), (14, 1), (15, –11), (15, 17), (17, –18), (17, –12), (17, 3), (17, 14), (18, –1), (19, –14), (19, –3), (19, 12), (19, 18), (20, –3)

69

(3, 16), (6, –5), (7, –10), (9, –17), (10, –19), (13, –19), (15, –14), (18, 1), (19, 8), (20, –7)

75

(3, –8), (7, –13), (19, –7)

77

(1, 1), (1, 12), (1, 15), (2, –17), (3, –19), (4, 9), (5, –8), (6, 1), (7, –3), (7, –2), (7, 5), (7, 8), (7, 20), (8, –13), (9, –17), (9, 2), (9, 4), (11, –19), (11, –18), (11, –13), (11, –6), (11, 1), (11, 3), (11, 9), (11, 15), (11, 16), (12, –5), (13, –6), (13, 5), (13, 15), (14, 3), (15, –13), (15, –2), (17, –19), (17, 3), (19, –12), (19, –8), (19, 20)

81

(7, –16), (11, 20), (14, 17)

85

(1, 1), (1, 6), (4, 11), (5, –3), (5, 4), (5, 8), (7, –18), (7, –12), (7, –2), (8, –7), (8, 13), (9, –4), (9, –2), (10, –1), (11, 2), (11, 12), (11, 18), (12, –13), (13, –6), (13, –1), (14, 13), (15, –13), (15, 7), (15, 19), (16, 1), (17, –18), (17, –13), (17, –12), (17, –11), (17, –8), (17, –7), (17, –6), (17, 2), (17, 3), (17, 14), (18, –11), (19, –13), (19, 7), (20, 3)

87

(3, 19), (6, –11), (7, –19), (11, 17), (14, 11), (17, 14)

91

(1, 1), (2, –3), (3, –4), (3, 16), (4, 3), (5, –1), (5, 4), (7, –16), (7, –1), (7, 10), (7, 12), (7, 18), (8, –9), (9, –10), (9, –5), (10, 3), (10, 9), (11, 10), (11, 15), (11, 17), (12, –19), (12, –17), (13, –17), (13, –16), (13, –10), (13, –9), (13, –3), (13, 1), (13, 4), (13, 12), (14, –19), (15, –16), (16, –17), (17, –12), (17, 3), (17, 8), (17, 16), (18, 17), (19, –3), (19, –1)

93

(3, –11), (11, 14), (14, 5), (15, 4), (17, 5), (18, 7)

95

(1, –18), (1, 1), (3, –16), (4, –3), (5, –17), (5, –16), (5, –13), (5, 2), (6, 17), (9, –14), (9, –7), (11, –4), (11, 7), (11, 13), (13, –7), (13, –2), (14, –13), (14, 3), (15, –11), (17, 2), (17, 4), (17, 14), (18, 13), (19, –12), (19, –9), (19, –4), (19, –2), (19, 2), (19, 12), (20, –9), (20, 13)

99

(9, –20), (9, 2), (9, 13), (11, –7), (11, 20), (14, –1), (17, –4), (18, 19)

 

Contattami

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