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

Pseudoprimi forti di Lucas

Sequenze  Teoria dei numeri 

Se Un è la sequenza di Lucas generalizzata generata da P e Q, con P e Q interi non nulli e P2 diverso da 4Q, Vn è la sequenza associata e D = P2 – 4Q, dato un numero dispari n che non abbia divisori comuni con D e Q, rappresentiamo n meno il simbolo di Jacobi (D | n), dove Simbolo di Jacobi (D | n) è il simbolo di Jacobi, come k2m, con k dispari: se n è primo, Uk ≡ 0 mod n o V2sk ≡ 0 mod n per un intero non negativo s minore di m. Se un numero composto dispari n, primo rispetto a DQ, soddisfa una delle due congruenze, n si dice “pseudoprimo forte di Lucas” rispetto a P e Q.

 

Tutti gli pseudoprimi forti di Lucas rispetto a P e Q sono pseudoprimi di Eulero – Lucas rispetto agli stessi P e Q (Robert Baillie e Samuel S. Wagstaff Jr., 1980).

L’inverso non è sempre vero, però se n è pseudoprimo di Eulero – Lucas rispetto a P e QSimbolo di Jacobi (Q | n) = –1 oppure m = 1, allora n è pseudoprimo forte di Lucas rispetto agli stessi P e Q (Robert Baillie e Samuel S. Wagstaff Jr., 1980).

 

Se n è pseudoprimo di Lucas (I) rispetto a P e Q, non ha divisori comuni con Q, è pseudoprimo di Eulero (I) rispetto a Q e U(n) meno il simbolo di Jacobi (D | n) è multiplo di n, n è pseudoprimo forte di Lucas rispetto agli stessi P e Q.

 

Arnault dimostrò nel 1997 che un numero composto è pseudoprimo forte di Lucas rispetto al massimo a 4 / 15 delle possibili coppie (P, Q), a meno che sia il prodotto di due primi gemelli con particolari proprietà.

 

Se D è positivo, ma non è un quadrato e P e Q sono primi tra loro, esiste una costante c, che dipende da P e Q, tale che il numero di pseudoprimi forti di Lucas rispetto a P e Q, non maggiori di n è maggiore di clogn, per n abbastanza grande (Robert Baillie e Samuel S. Wagstaff Jr., 1980).

 

Se D non è 0, –Q, –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 (D | n0) = m contiene infiniti interi n, che sono pseudoprimi forti di Lucas rispetto a P e Q con Simbolo di Jacobi (D | n) = m e il numero di tali pseudoprimi non maggiori di x è maggiore di c * log(x) / log(log(x)), per una costante c che dipende da P, Q, a, b e m (Andrzej Rotkiewicz e A. Schinzel, 2000).

 

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 (D | n0) = m contiene infiniti interi n, che sono pseudoprimi forti di Lucas rispetto a P e Q con Simbolo di Jacobi (D | n) = m e contemporaneamente anche pseudoprimi di Lucas, pseudoprimi di Lucas di seconda speciepseudoprimi di Dicksonpseudoprimi di Dickson di seconda specie e il numero di tali pseudoprimi non maggiori di x è maggiore di c * log(x) / log(log(x)), per una costante c che dipende da P, a e b (Andrzej Rotkiewicz, 2000).

Contattami

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