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

Pseudoprimi di Lehmer

Sequenze  Teoria dei numeri 

Le sequenze di Lehmer sono analoghe a quelle di Lucas: scelti due interi P e Q, si definisce la sequenza di Lehmer Un(P, Q) come:

  • U0(P, Q) = 0,

  • U1(P, Q) = 1,

  • Un + 1(P, Q) = PUn(P, Q) – QUn – 1(P, Q) per n pari e maggiore di 0,

  • Un + 1(P, Q) = Un(P, Q) – QUn – 1(P, Q) per n dispari e maggiore di 0.

La sequenza associata è definita come:

  • V0(P, Q) = 2,

  • V1(P, Q) = P,

  • Vn + 1(P, Q) = PVn(P, Q) – QVn – 1(P, Q) per n pari e maggiore di 0,

  • Vn + 1(P, Q) = Vn(P, Q) – QVn – 1(P, Q) per n dispari e maggiore di 0.

 

La sequenza di Lehmer equivale a Un(P, Q) = (α^n – β^n) / (α^2 – β^2) per n pari e Un(P, Q) = (α^n – β^n) / (α – β) per n dispari; la sequenza associata equivale a Vn(P, Q) = αn + βn per n pari e Vn(P, Q) = (α^n + β^n) / (α + β) per n dispari, dove α = (sqrt(P + sqrt(D)) / 2 e β = (sqrt(P – sqrt(D)) / 2, con D = P – 4Q.

 

Se n è un primo dispari, senza divisori comuni con Q e D, allora U(n – (D | n)) ≡ mod n, dove Simbolo di Jacobi (D | n) rappresenta il simbolo di Jacobi. Quindi per ogni primo dispari che non divide Q, esiste un multiplo che appartiene alla sequenza di Lehmer, mentre lo stesso non vale per la sequenza associata; in particolare se P = Q + 1 o se P = 1 e Q = –1, i numeri della sequenza associata sono multipli solo di 2 / 3 dei primi (Lagarias, 1985).

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

 

E’ stato dimostrato che n è pseudoprimo di Lehmer, rispetto a P e Q se e solo se è pseudoprimo di Lucas (I), rispetto a P e PQ (Jon Grantham, 2000).

Contattami

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