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

Pseudoprimi di Lucas (I)

Sequenze  Teoria dei numeri 

Date una sequenza di Lucas generalizzata definita come U0 = 0, U1 = 1, Un + 1 = PUnQUn – 1 e la sequenza associata definita come V0 = 2, V1 = P, Vn + 1 = PVnQVn – 1 con P e Q interi non nulli e P2 diverso da 4Q, e definendo D = P2 – 4Q, se n un numero primo dispari che non divide DQ, valgono le seguenti congruenze, nelle quali Simbolo di Jacobi (D | n) rappresenta il simbolo di Jacobi:

  • Congruenza soddisfatta da un primo dispari n;

  • Congruenza soddisfatta da un primo dispari n;

  • VnP mod n;

  • Congruenza soddisfatta da un primo dispari n.

Se n è primo rispetto a 2DPQ, tra le prime tre congruenze due implicano la restante.

L’ultima congruenza è sempre soddisfatta se n è il quadrato di un primo p, Q = 1 e D è un residuo quadratico modulo p (Robert Baillie e Samuel S. Wagstaff Jr., 1980).

 

Se un numero composto dispari, primo rispetto a DQ, soddisfa la prima congruenza per qualche valore di P e Q, si chiama “pseudoprimo di Lucas”, rispetto a P e Q.

E’ relativamente normale per un numero composto essere pseudoprimo di Lucas; Lieuwens dimostrò nel 1971 che, fissati P, Q e un intero k maggiore di 1, esistono infiniti pseudoprimi, ciascuno di quali prodotto di esattamente k fattori primi.

 

Nel 1964 E. Lehmer dimostrò che esistono infiniti pseudoprimi di Lucas rispetto a 1 e –1 (v. pseudoprimi di Fibonacci).

 

Se si ammettono pseudoprimi di Lucas pari, non ne esistono rispetto a –1 e 1 (A. Di Porto, 1993), né rispetto a 1 e 1 (R. André-Jeannin, 1996), ma ne esiste almeno uno per qualsiasi altra combinazione di P e Q, entrambi dispari (R. André-Jeannin, 1996).

 

Nel 1977 Hugh Williams dimostrò che, fissato D della forma 4k o 4k + 1, per ogni numero composto n primo rispetto a D esiste almeno una coppia di interi P, Q, con D = P2 – 4Q e Q primo sia rispetto a P, sia a n, tale che n non sia pseudoprimo di Lucas rispetto a P e Q.

Kiss, Phong e Liewens dimostrarono nel 1986 che per ogni intero n e per ogni sequenza di Lucas non degenere (cioè non formata da tutti zeri), esistono infiniti pseudoprimi che hanno esattamente n fattori primi distinti; inoltre, se D è positivo, fissato un intero a, i fattori possono essere tutti della forma na + 1. Non esistono quindi pseudoprimi di Lucas assoluti, cioè che siano pseudoprimi rispetto a qualsiasi coppia di valori P e Q, come invece avviene per gli pseudoprimi di Fermat (v. numeri di Carmichael), quindi un esame di primalità basato sulle congruenze indicate è potenzialmente migliore di uno basato sul piccolo teorema di Fermat.

 

Robert Baillie e Samuel S. Wagstaff Jr. dimostrarono nel 1980 che per ogni intero composto n, fissato D, con D mod 4 = 0 o 1, il numero di valori di P tra 1 e n (inclusi) per i quali esiste almeno un valore di Q con P2 – 4QD mod n, tale che n sia pseudoprimo di Lucas rispetto a P e Q è Numero di valori di P per i quali esiste almeno un valore di Q tale che n sia pseudoprimo di Lucas rispetto a P e Q, dove il prodotto va calcolato su tutti i divisori primi di nSimbolo di Jacobi (D | n) è il simbolo di Jacobi. In particolare, per ogni valore di D, esistono almeno 3 coppie di interi P e Q, tali che n sia pseudoprimo di Lucas rispetto a loro.

 

Robert Baillie e Samuel S. Wagstaff Jr. dimostrarono nel 1980 che, fissati P e Q, gli pseudoprimi di Lucas minori di n sono meno di Limite superiore per il numeri di pseudoprimi di Lucas minori di n per una costante c e n abbastanza grande. Una conseguenza è che la somma dei reciproci degli pseudoprimi di Lucas rispetto a P e Q fissati è convergente.

 

Per qualsiasi valore fissato di P e Q, il numero degli pseudoprimi di Lucas minori di n è inferiore a Limite superiore per il numeri di pseudoprimi di Lucas minori di n (D.M. Gordon e Carl Pomerance, 1991) e per n abbastanza grande è maggiore di elogcx, per una costante c, se la sequenza non è degenere, ossia se |P2 – 2Q| è diverso da 0, Q o 2Q (P. Erdös, P. Kiss e A. Sárközy, 1988).

 

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

Pseudoprimo

(P, Q)

9

(1, –4), (1, +5), (2, –7), (2, +2), (4, –1), (4, +8), (5, –1), (5, +8), (7, –7), (7, +2), (8, –4), (8, +5)

15

(1, –7), (1, +8), (2, –13), (2, +2), (3, –8), (3, +7), (4, –7), (4, +8), (5, –4), (5, –1), (5, +11), (5, +14), (6, –2), (6, +13), (7, –13), (7, +2), (8, –13), (8, +2), (9, –2), (9, +13), (10, –4), (10, –1), (10, +11), (10, +14), (11, –7), (11, +8), (12, –8), (12, +7), (13, –13), (13, +2), (14, –7), (14, +8)

21

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

25

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

27

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

33

(1, –16), (1, +17), (2, +2), (3, +10), (4, +8), (5, –4), (6, +7), (7, +8), (8, –1), (9, –20), (9, +13), (10, –16), (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), (16, –4), (17, –4), (18, –14), (18, +19), (19, –1), (20, +2)

35

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

39

(1, –19), (1, +20), (2, +2), (3, –2), (4, +8), (5, –7), (6, –8), (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), (14, +20), (15, –11), (16, +11), (17, +8), (18, –20), (18, +19), (19, +5), (20, +5)

45

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

49

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

51

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

55

(1, –18), (1, +1), (1, +12), (2, –17), (2, –7), (2, –6), (2, +2), (2, +4), (3, –2), (3, +3), (3, +9), (3, +14), (4, –13), (4, +8), (4, +16), (5, –8), (5, –4), (5, +3), (5, +12), (6, –19), (6, –8), (6, +1), (6, +12), (6, +18), (7, –17), (7, –6), (7, –3), (7, –2), (7, +9), (8, –2), (8, +3), (8, +9), (8, +14), (9, –18), (9, +13), (9, +16), (10, –18), (10, –16), (10, –7), (10, +6), (10, +12), (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, +4), (12, +17), (13, –17), (13, –7), (13, –6), (13, +2), (13, +4), (14, –19), (14, –13), (14, –12), (14, –8), (15, –17), (15, –14), (15, –13), (15, –2), (15, +19), (16, –19), (16, –8), (16, +1), (16, +12), (16, +18), (17, +3), (17, +7), (17, +14), (18, –17), (18, –6), (18, –3), (18, –2), (18, +9), (19, –19), (19, –13), (19, –12), (19, –8), (20, –18), (20, –17), (20, –9), (20, –7)

57

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

63

(1, –4), (2, –16), (2, +2), (4, –1), (4, +8), (5, –19), (5, +17), (7, +2), (7, +11), (8, –4), (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), (10, +5), (11, –16), (11, +20), (13, –10), (13, –1), (13, +17), (14, –19), (14, –10), (14, +8), (16, –16), (16, +2), (17, –13), (17, +5), (18, –20), (18, –16), (18, –13), (18, –8), (18, –2), (18, –1), (18, +1), (18, +5), (18, +8), (18, +13), (18, +19), (18, +20), (19, –4), (19, +5), (20, +11), (20, +20)

65

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

69

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

75

(2, +2), (3, –8), (4, +8), (7, –13), (19, –7)

77

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

81

(2, +2), (4, +8), (7, –16), (11, +20), (14, +17)

85

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

87

(2, +2), (3, +19), (4, +8), (6, –11), (7, –19), (11, +17), (14, +11), (17, +14)

91

(1, +1), (2, –3), (2, +2), (2, +4), (3, –4), (3, +3), (3, +9), (3, +16), (4, –12), (4, +3), (4, +8), (4, +16), (5, –1), (5, +4), (6, –16), (6, +12), (6, +18), (7, –16), (7, –1), (7, +10), (7, +12), (7, +18), (8, –9), (8, +12), (9, –10), (9, –5), (10, –4), (10, +3), (10, +9), (10, +16), (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), (14, –6), (14, –4), (15, –16), (15, –9), (16, –17), (16, –10), (17, –12), (17, +3), (17, +8), (17, +16), (18, –20), (18, +17), (19, –3), (19, –1), (20, –16), (20, +12), (20, +18)

93

(2, +2), (3, –11), (4, +8), (11, +14), (12, +10), (14, +5), (15, +4), (17, +5), (18, +7), (20, +14)

95

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

99

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

 

Se un numero composto dispari primo rispetto a DQ soddisfa la seconda congruenza per qualche valore di P e Q, si chiama “pseudoprimo di Lucas di seconda specie”, rispetto a P e Q.

M. Yorinaga dimostrò che esistono infiniti pseudoprimi di Lucas di seconda specie”, rispetto a 1 e –1.

 

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

Pseudoprimo

(P, Q)

9

(1, –7), (1, +2), (2, –4), (2, +5), (3, –8), (3, –1), (3, +1), (3, +8), (4, –1), (4, +8), (5, –1), (5, +8), (6, –8), (6, –1), (6, +1), (6, +8), (7, –4), (7, +5), (8, –7), (8, +2)

15

(1, –13), (1, +2), (4, –13), (4, +2), (11, –13), (11, +2), (14, –13), (14, +2)

21

(4, –4), (4, +17), (9, –2), (9, +19), (10, –4), (10, +17), (11, –4), (11, +17), (12, –2), (12, +19), (17, –4), (17, +17)

25

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

27

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

33

(2, +5), (3, +10), (8, –1), (9, –19), (9, –17), (9, +14), (9, +16), (11, –10), (13, +5), (14, –1), (19, –1), (20, +5)

35

(1, +1), (3, –16), (3, –6), (3, +19), (5, –1), (6, +1), (15, –4), (17, –16), (17, –6), (17, +19), (18, –16), (18, –6), (18, +19), (20, –4)

39

(1, +2), (3, +8), (7, +11), (10, –16), (14, +2), (15, –8), (16, –16), (19, +11), (20, +11)

45

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

49

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

51

(2, +5), (6, –16), (7, –1), (8, +14), (9, –20), (10, –1), (15, +20), (17, –16), (19, +5)

55

(1, +1), (4, –9), (5, +1), (5, +19), (14, +6), (19, +6)

57

(1, +2), (2, +5), (6, –20), (8, +8), (11, +8), (13, –1), (17, +5), (18, –17), (19, +20), (20, +2)

63

(3, +1), (14, –1), (18, +1)

65

(1, +1), (1, +2), (4, –12), (4, +8), (5, –2), (6, +18), (7, –8), (7, +12), (8, –2), (8, –1), (9, –12), (9, +8), (12, +14), (13, +8), (13, +12), (13, +18), (14, +1), (14, +2), (17, –18), (18, –2), (18, –1), (19, +18), (20, –14), (20, –1)

69

(1, +2), (3, +10), (11, –16), (12, +5), (14, –10), (15, +19), (17, +14)

75

(1, –13), (9, +7), (11, +17), (12, –7), (14, +17), (15, –1), (15, +1), (19, +2)

77

(1, +1), (6, –20), (8, –4), (10, –13), (11, +12), (17, +8), (17, +12)

81

(1, +20), (3, –19), (3, –17), (6, +8), (6, +10), (9, –1), (9, +1), (10, –16), (13, –19), (14, +8), (17, +11), (18, –1), (18, +1)

85

(1, +1), (3, –3), (4, –19), (4, +16), (5, –14), (5, +4), (10, –18), (10, +12), (12, –13), (13, –1), (14, +13), (16, +1), (17, –18), (17, +13), (18, –16), (18, +19), (20, –4), (20, +14)

87

(3, +8), (9, –7), (10, +14), (13, –4), (16, –4), (19, +14)

91

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

93

(3, +8), (4, +17), (9, –13), (13, –16), (14, +11), (17, +11)

95

(1, +1), (13, –1), (13, +14), (15, –1), (15, +11)

99

(3, +10), (7, –13), (12, –1), (14, –1), (15, –1), (18, –1)

 

Se un numero composto dispari primo rispetto a DQ soddisfa la terza congruenza per qualche valore di P e Q, si chiama “pseudoprimo di Dickson”, rispetto a P e Q.

Gli pseudoprimi di Dickson rispetto a 1 e –1 sono talvolta chiamati “pseudoprimi di Lucas”.

 

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

Pseudoprimo

(P, Q)

9

(4, –7), (4, –4), (4, –1), (4, +2), (4, +5), (4, +8), (5, –7), (5, –4), (5, –1), (5, +2), (5, +5), (5, +8)

21

(3, –16), (3, –2), (3, +5), (3, +19), (18, –16), (18, –2), (18, +5), (18, +19), (1, –19), (1, –14)

25

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

27

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

33

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

35

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

39

(3, –19), (3, +7), (3, +20), (6, –10), (6, +16), (9, –8), (9, +5), (18, –5), (18, +8)

45

(9, –17), (9, –7), (9, –2), (9, +8), (9, +13), (18, –13), (18, –8), (18, +2), (18, +7), (18, +17), (1, –20)

49

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

51

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

55

(1, +1), (9, –19), (10, +1), (10, +12), (11, –19), (11, –14), (11, –9), (11, –4), (11, +1), (11, +6), (11, +16), (20, –19), (20, –8), (20, +3), (20, +14)

57

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

63

(18, –20), (18, –13), (18, +1), (18, +8), (1, –12)

65

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

69

(3, –5), (6, –19), (6, +4), (9, –4), (9, +19), (12, +17), (15, –2), (18, +8)

77

(1, +1), (5, –16), (12, +12), (16, –16)

85

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

87

(3, –7), (6, +2), (9, +17), (12, –20), (15, +7), (18, +11)

91

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

93

(3, +13), (12, –4), (15, –8)

95

(1, +1), (16, +11), (19, –14), (19, –9), (19, –4), (19, +1), (19, +6), (19, +11), (19, +16), (20, –18), (20, +1)

99

(4, –10), (14, –13), (14, –10), (14, –1), (14, +20), (18, –10), (18, +1)

 

Se un numero composto dispari primo rispetto a DQ soddisfa la quarta congruenza per qualche valore di P e Q, si chiama “pseudoprimo di Dickson di seconda specie”, rispetto a P e Q.

 

La tabella seguente mostra gli pseudoprimi di Dickson di seconda specie fino a 100 rispetto a P da 1 a 20 e Q da –20 a 20.

Pseudoprimo

(P, Q)

9

(1, –1), (1, +8), (2, –1), (2, +8), (3, –8), (3, –1), (3, +1), (3, +8), (4, –1), (4, +8), (5, –1), (5, +8), (6, –8), (6, –1), (6, +1), (6, +8), (7, –1), (7, +8), (8, –1), (8, +8)

15

(3, –7), (5, –1), (10, –1), (12, –7)

21

(3, –5), (9, –4), (12, –4), (18, –5), (1, –18)

25

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

27

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

33

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

35

(1, +1), (2, –1), (6, +1), (7, –1), (9, +12), (10, –6), (12, –1), (16, +12), (19, +12)

39

(9, –19), (9, –4), (9, +20), (12, –7), (13, –1), (15, –10)

45

(3, –8), (3, +17), (6, –17), (6, +8), (9, –17), (9, +8), (12, –8), (12, +17), (15, –19), (15, –1), (15, +1), (15, +19), (18, –8), (18, +17), (1, –18)

49

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

51

(5, +11), (9, +14), (11, +11), (12, +20), (18, –7)

55

(1, +1), (6, +17), (12, –17), (16, +17)

57

(2, +8), (3, –11), (3, –8), (4, +11), (6, –20), (6, +17), (13, –1), (15, –10), (15, –8), (16, +8), (16, +11), (17, +8), (19, +20)

63

(1, –1), (3, –1), (3, +1), (4, –1), (6, –1), (8, –1), (10, –1), (11, –1), (13, –1), (15, –1), (17, –1), (18, –1), (18, +1), (20, –1)

65

(1, +1), (4, +8), (6, +18), (7, –8), (9, +8), (12, +14), (13, –12), (13, +12), (14, +1), (17, –18), (17, –12), (19, +18), (20, –9)

69

(9, –16), (12, –14), (15, –8), (15, +8)

75

(3, +13), (7, +8), (15, –1), (15, +1)

77

(1, +1), (12, –2), (1, +8)

81

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

85

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

87

(6, –10), (12, –16), (15, +13), (17, –13), (18, –13)

91

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

93

(6, –11), (9, –7)

95

(1, +1), (2, –12), (2, –6), (4, +6), (7, –6), (12, –6), (16, +6), (17, –12), (17, –6), (20, –11), (20, –6)

99

(2, +17), (3, +10), (8, +17), (13, +17), (14, +17), (19, +17), (20, +17)

 

Se D è un quadrato, ogni numero di Carmichael che non abbia divisori in comune con DQ è pseudoprimo di Lucas, pseudoprimo di Lucas di seconda specie, pseudoprimo di Dickson e pseudoprimo di Dickson di seconda specie rispetto a qualsiasi sequenza con quel valore di D.

 

Se Q = ±1 e D non è 0, –2Q o –3Q, ogni progressione aritmetica del tipo ak + b con a e b primi tra loro, che contenga un intero n0 tale che Simbolo di Jacobi (Q | n0) uguale a m, dove Simbolo di Jacobi (Q | n) è il simbolo di Jacobi, contiene infiniti interi n con Simbolo di Jacobi (Q | n) uguale a m, che sono contemporaneamente pseudoprimi forti di Lucas (e quindi pseudoprimi di Lucas), pseudoprimi di Lucas di seconda specie, pseudoprimi di Dickson e pseudoprimi di Dickson di seconda specie rispetto a P e Q e il numero di tali pseudoprimi non maggiori di x è maggiore di Limite inferiore per il numero di pseudoprimi non maggiori di x, per una costante c che dipende da P, a e b (Andrzej Rotkiewicz, 2000).

 

Se Q = ±1 e se P e Q non sono entrambi 1, esistono infiniti interi che sono contemporaneamente pseudoprimi di Lucas, pseudoprimi di Lucas di seconda specie e pseudoprimi di Dickson rispetto a P e Q (Andrzej Rotkiewicz, 1973).

Il minimo intero che sia pseudoprimo di Lucas, pseudoprimo di Lucas di seconda specie, pseudoprimo di Dickson e pseudoprimo di Dickson di seconda specie rispetto a 1 e –1 è 4181 = 37 • 113.

 

La tabella seguente mostra i numeri che sono pseudoprimi di Lucas, pseudoprimi di Lucas di seconda specie, pseudoprimi di Dickson e pseudoprimi di Dickson di seconda specie fino a 100 rispetto a P da 1 a 100 e Q da –100 a 100.

Pseudoprimo

(P, Q)

9

(4, –1), (4, +8), (5, –1), (5, +8)

25

(1, –24), (1, +1), (2, –7), (2, +18), (6, –7), (6, +18), (7, –1), (7, +24), (8, –18), (8, +7), (11, –18), (11, +7), (14, –18), (14, +7), (17, –18), (17, +7), (18, –1), (18, +24), (19, –7), (19, +18), (23, –7), (23, +18), (24, –24), (24, +1)

27

(5, +26), (22, +26)

33

(3, –23), (3, +10), (8, –1), (8, +32), (11, –10), (11, +23), (14, –1), (14, +32), (19, –1), (19, +32), (22, –10), (22, +23), (25, –1), (25, +32), (30, –23), (30, +10)

35

(1, +1), (6, +1), (29, +1), (34, +1)

45

(9, –37), (9, –17), (9, +8), (9, +28), (18, –28), (18, –8), (18, +17), (18, +37), (27, –28), (27, –8), (27, +17), (27, +37), (36, –37), (36, –17), (36, +8), (36, +28)

49

(1, –48), (1, +1), (6, –31), (6, +18), (9, –30), (9, +19), (10, –48), (10, +1), (12, –18), (12, –1), (12, +31), (12, +48), (15, –18), (15, +31), (16, –19), (16, +30), (17, –30), (17, –18), (17, +19), (17, +31), (18, –19), (18, +30), (19, –31), (19, +18), (20, –30), (20, –1), (20, +19), (20, +48), (24, –1), (24, +48), (25, –1), (25, +48), (29, –30), (29, –1), (29, +19), (29, +48), (30, –31), (30, +18), (31, –19), (31, +30), (32, –30), (32, –18), (32, +19), (32, +31), (33, –19), (33, +30), (34, –18), (34, +31), (37, –18), (37, –1), (37, +31), (37, +48), (39, –48), (39, +1), (40, –30), (40, +19), (43, –31), (43, +18), (48, –48), (48, +1)

51

(7, +50), (10, +50), (17, +35), (24, +16), (27, +16), (34, +35), (41, +50), (44, +50)

55

(1, –54), (1, +1), (21, –54), (21, +1), (34, –54), (34, +1), (54, –54), (54, +1)

57

(6, –20), (6, +37), (13, –1), (13, +56), (19, –37), (19, +20), (25, –1), (25, +56), (32, –1), (32, +56), (38, –37), (38, +20), (44, –1), (44, +56), (51, –20), (51, +37)

63

(18, +1), (45, +1)

65

(1, +1), (4, –57), (4, +8), (6, –47), (6, +18), (7, –8), (7, +57), (8, +64), (9, –57), (9, +8), (12, +14), (13, –53), (13, –38), (13, +12), (13, +27), (14, +1), (17, –18), (17, +47), (18, +64), (19, –47), (19, +18), (20, –34), (20, –21), (20, +31), (20, +44), (21, +51), (22, –18), (22, +47), (26, –27), (26, –12), (26, +38), (26, +53), (27, +14), (30, –44), (30, –31), (30, +21), (30, +34), (31, +51), (32, –8), (32, +57), (33, –8), (33, +57), (34, +51), (35, –44), (35, –31), (35, +21), (35, +34), (38, +14), (39, –27), (39, –12), (39, +38), (39, +53), (43, –18), (43, +47), (44, +51), (45, –34), (45, –21), (45, +31), (45, +44), (46, –47), (46, +18), (47, +64), (48, –18), (48, +47), (51, +1), (52, –53), (52, –38), (52, +12), (52, +27), (53, +14), (56, –57), (56, +8), (57, +64), (58, –8), (58, +57), (59, –47), (59, +18), (61, –57), (61, +8), (64, +1)

75

(25, +26), (50, +26)

77

(1, +1), (34, +1), (43, +1), (76, +1)

81

(22, –1), (22, +80), (59, –1), (59, +80)

85

(1, –84), (1, +1), (3, –38), (3, +47), (4, –69), (4, +16), (5, –81), (5, –64), (5, +4), (5, +21), (12, –13), (12, +72), (13, –1), (13, +84), (14, –72), (14, +13), (16, –84), (16, +1), (17, –33), (17, –18), (17, +52), (17, +67), (18, –16), (18, +69), (20, –21), (20, –4), (20, +64), (20, +81), (21, –69), (21, +16), (22, –13), (22, +72), (29, –47), (29, +38), (31, –72), (31, +13), (33, –16), (33, +69), (34, –67), (34, –52), (34, +18), (34, +33), (37, –38), (37, +47), (38, –1), (38, +84), (39, –47), (39, +38), (46, –47), (46, +38), (47, –1), (47, +84), (48, –38), (48, +47), (51, –67), (51, –52), (51, +18), (51, +33), (52, –16), (52, +69), (54, –72), (54, +13), (56, –47), (56, +38), (63, –13), (63, +72), (64, –69), (64, +16), (65, –21), (65, –4), (65, +64), (65, +81), (67, –16), (67, +69), (68, –33), (68, –18), (68, +52), (68, +67), (69, –84), (69, +1), (71, –72), (71, +13), (72, –1), (72, +84), (73, –13), (73, +72), (80, –81), (80, –64), (80, +4), (80, +21), (81, –69), (81, +16), (82, –38), (82, +47), (84, –84), (84, +1)

91

(1, –90), (1, –51), (1, +1), (1, +40), (2, –29), (2, –3), (2, +62), (2, +88), (3, –82), (3, –4), (3, +9), (3, +87), (4, –88), (4, –75), (4, +3), (4, +16), (5, –87), (5, –22), (5, +4), (5, +69), (6, –79), (6, –27), (6, +12), (6, +64), (7, –79), (7, –53), (7, –1), (7, +12), (7, +38), (7, +90), (8, –48), (8, –9), (8, +43), (8, +82), (9, –36), (9, –10), (9, +55), (9, +81), (10, –82), (10, –4), (10, +9), (10, +87), (11, –81), (11, –68), (11, +10), (11, +23), (12, –64), (12, –38), (12, +27), (12, +53), (13, –79), (13, –55), (13, –48), (13, –27), (13, –16), (13, –9), (13, +12), (13, +36), (13, +43), (13, +64), (13, +75), (13, +82), (14, –64), (14, –51), (14, –25), (14, +27), (14, +40), (14, +66), (15, –55), (15, –16), (15, +36), (15, +75), (16, –43), (16, –17), (16, +48), (16, +74), (17, –88), (17, –75), (17, +3), (17, +16), (18, –74), (18, –61), (18, +17), (18, +30), (19, –66), (19, –1), (19, +25), (19, +90), (20, –79), (20, –27), (20, +12), (20, +64), (21, –74), (21, –22), (21, –9), (21, +17), (21, +69), (21, +82), (22, –62), (22, –23), (22, +29), (22, +68), (23, –43), (23, –17), (23, +48), (23, +74), (24, –81), (24, –68), (24, +10), (24, +23), (25, –25), (25, –12), (25, +66), (25, +79), (26, –87), (26, –66), (26, –29), (26, –22), (26, –3), (26, –1), (26, +4), (26, +25), (26, +62), (26, +69), (26, +88), (26, +90), (27, –90), (27, –51), (27, +1), (27, +40), (28, –81), (28, –29), (28, –16), (28, +10), (28, +62), (28, +75), (29, –69), (29, –30), (29, +22), (29, +61), (30, –36), (30, –10), (30, +55), (30, +81), (31, –74), (31, –61), (31, +17), (31, +30), (32, –53), (32, –40), (32, +38), (32, +51), (33, –66), (33, –1), (33, +25), (33, +90), (34, –48), (34, –9), (34, +43), (34, +82), (35, –88), (35, –36), (35, –23), (35, +3), (35, +55), (35, +68), (36, –69), (36, –30), (36, +22), (36, +61), (37, –29), (37, –3), (37, +62), (37, +88), (38, –25), (38, –12), (38, +66), (38, +79), (39, –81), (39, –74), (39, –68), (39, –61), (39, –53), (39, –40), (39, +10), (39, +17), (39, +23), (39, +30), (39, +38), (39, +51), (40, –64), (40, –38), (40, +27), (40, +53), (41, –55), (41, –16), (41, +36), (41, +75), (42, –43), (42, –30), (42, –4), (42, +48), (42, +61), (42, +87), (43, –62), (43, –23), (43, +29), (43, +68), (44, –87), (44, –22), (44, +4), (44, +69), (45, –53), (45, –40), (45, +38), (45, +51), (46, –53), (46, –40), (46, +38), (46, +51), (47, –87), (47, –22), (47, +4), (47, +69), (48, –62), (48, –23), (48, +29), (48, +68), (49, –43), (49, –30), (49, –4), (49, +48), (49, +61), (49, +87), (50, –55), (50, –16), (50, +36), (50, +75), (51, –64), (51, –38), (51, +27), (51, +53), (52, –81), (52, –74), (52, –68), (52, –61), (52, –53), (52, –40), (52, +10), (52, +17), (52, +23), (52, +30), (52, +38), (52, +51), (53, –25), (53, –12), (53, +66), (53, +79), (54, –29), (54, –3), (54, +62), (54, +88), (55, –69), (55, –30), (55, +22), (55, +61), (56, –88), (56, –36), (56, –23), (56, +3), (56, +55), (56, +68), (57, –48), (57, –9), (57, +43), (57, +82), (58, –66), (58, –1), (58, +25), (58, +90), (59, –53), (59, –40), (59, +38), (59, +51), (60, –74), (60, –61), (60, +17), (60, +30), (61, –36), (61, –10), (61, +55), (61, +81), (62, –69), (62, –30), (62, +22), (62, +61), (63, –81), (63, –29), (63, –16), (63, +10), (63, +62), (63, +75), (64, –90), (64, –51), (64, +1), (64, +40), (65, –87), (65, –66), (65, –29), (65, –22), (65, –3), (65, –1), (65, +4), (65, +25), (65, +62), (65, +69), (65, +88), (65, +90), (66, –25), (66, –12), (66, +66), (66, +79), (67, –81), (67, –68), (67, +10), (67, +23), (68, –43), (68, –17), (68, +48), (68, +74), (69, –62), (69, –23), (69, +29), (69, +68), (70, –74), (70, –22), (70, –9), (70, +17), (70, +69), (70, +82), (71, –79), (71, –27), (71, +12), (71, +64), (72, –66), (72, –1), (72, +25), (72, +90), (73, –74), (73, –61), (73, +17), (73, +30), (74, –88), (74, –75), (74, +3), (74, +16), (75, –43), (75, –17), (75, +48), (75, +74), (76, –55), (76, –16), (76, +36), (76, +75), (77, –64), (77, –51), (77, –25), (77, +27), (77, +40), (77, +66), (78, –79), (78, –55), (78, –48), (78, –27), (78, –16), (78, –9), (78, +12), (78, +36), (78, +43), (78, +64), (78, +75), (78, +82), (79, –64), (79, –38), (79, +27), (79, +53), (80, –81), (80, –68), (80, +10), (80, +23), (81, –82), (81, –4), (81, +9), (81, +87), (82, –36), (82, –10), (82, +55), (82, +81), (83, –48), (83, –9), (83, +43), (83, +82), (84, –79), (84, –53), (84, –1), (84, +12), (84, +38), (84, +90), (85, –79), (85, –27), (85, +12), (85, +64), (86, –87), (86, –22), (86, +4), (86, +69), (87, –88), (87, –75), (87, +3), (87, +16), (88, –82), (88, –4), (88, +9), (88, +87), (89, –29), (89, –3), (89, +62), (89, +88), (90, –90), (90, –51), (90, +1), (90, +40)

95

(1, +1), (39, +1), (56, +1), (94, +1)

99

(14, +98), (22, +89), (36, +10), (41, +98), (58, +98), (63, +10), (77, +89), (85, +98)

 

 Tra i problemi aperti:

  • le sequenze di Lucas generalizzate si possono ottenere come Formula per le sequenze di Lucas generalizzate e le sequenza associate come Vn(P, Q) = αn + βn, dove Formula per α e Formula per β; se D è un quadrato, P e Q sono diversi da α ± 1 e ±α e β è diverso da ±1, non è noto se ogni progressione aritmetica del tipo an + b, con a e b fissati e privi di divisori comuni, contenga infiniti pseudoprimi di Lucas di seconda specie, pseudoprimi di Dickson e pseudoprimi di Dickson di seconda specie rispetto a P e Q;

  • se D è un quadrato e P e Q sono diversi da ±1, non è noto se esistano infiniti pseudoprimi di Lucas di seconda specie, pseudoprimi di Dickson e pseudoprimi di Dickson di seconda specie rispetto a P e Q;

  • se D è un quadrato e P e Q sono diversi da ±1, non è noto se esistano infinite progressioni aritmetiche di tre pseudoprimi di Dickson rispetto a P e Q;

  • per Q diverso da ±1 esistono infiniti numeri composti dispari n primi rispetto a DPQ con Simbolo di Jacobi (D | n) = –1, dove Simbolo di Jacobi (D | n) è il simbolo di Jacobi.

 

Dato che gli pseudoprimi di Lucas sembrano più rari degli pseudoprimi di Fermat e non esistono pseudoprimi di Lucas rispetto a tutte le sequenze di Lucas generalizzate, Robert Baillie e Samuel S. Wagstaff Jr. suggerirono nel 1980 un esame di primalità per stabilire se un intero è probabilmente primo, più efficace di quello basato sui primi di Fermat. L’efficacia del metodo dipende dalla scelta di P e Q, per la quale sono stati suggeriti alcuni metodi:

  • prendere per D il primo elemento della sequenza dei numeri dispari a segni alternati 5, –7, 9, –11, 13, –15, … tale che Simbolo di Jacobi (D | n) = –1, quindi prendere P = 1 e Q = (1 – D) / 4 (Selfridge);

  • prendere per D il primo numero dispari maggiore di 3 tale che Simbolo di Jacobi (D | n) = –1, quindi prendere per P il minimo numero dispari maggiore della radice quadrata di DQ = (P^2 – D) / 4 (Baillie e Wagstaff).

E’ importante che D non sia un residuo quadratico modulo n, altrimenti l’esame equivale a un esame di primalità basato sul piccolo teorema di Fermat in base Q – 1.

I metodi falliscono se n è un quadrato, perché in tal caso Simbolo di Jacobi (D | n) non è mai –1, ma questa eventualità può essere velocemente esaminata a parte.

Baillie e Wagstaff suggerirono di esaminare prima i divisori minori di 1000 e di verificare che n sia uno pseudoprimo forte in base 2, dopodichè l’esame da loro proposto non commette errori nell’identificazione dei numeri primi fino a 25 • 109; teoricamente potrebbe identificare come primo un numero composto, ma non il contrario.

Un ulteriore miglioramento consiste nello scartare i casi nei quali la procedura suggerisce produce Q = ±1.

Si conoscono pseudoprimi di Fermat che sono anche pseudoprimi di Lucas; per esempio, 341 = 11 • 31 è pseudoprimo di Fermat in base 2 e pseudoprimo di Lucas rispetto a 7 e 2.

Contattami

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