Pseudoprimo di Eulero

Niente fonti!
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

Un numero n è detto pseudoprimo di Eulero in base a (con MCD(n,a)=1) se è un numero dispari composto e

a n − 1 2 ≡ ± 1 mod n {\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1\mod n}

dove mod è l'operazione modulo.

Questi numeri sono detti pseudoprimi perché tutti i numeri primi verificano questa proprietà, in base al piccolo teorema di Fermat. Infatti, secondo questo ogni numero a coprimo con n verifica

a p − 1 ≡ 1 mod p {\displaystyle a^{p-1}\equiv 1\mod p}

Se ora p>2, si ha

a 2 ⋅ p − 1 2 ≡ 1 mod p {\displaystyle a^{2\cdot {\frac {p-1}{2}}}\equiv 1\mod p} , ovvero a p − 1 2 ≡ ± 1 mod p {\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1\mod p}

Una forma più forte della relazione precedente è

a n − 1 2 ≡ ( a n ) {\displaystyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right)}

dove (a/n) è il simbolo di Legendre. Un numero che verifica questa uguaglianza è detto pseudoprimo di Eulero-Jacobi in base a. Ogni pseudoprimo di Eulero-Jacobi è anche uno pseudoprimo di Eulero, poiché il simbolo di Legendre può essere solamente 1 e -1, tuttavia esistono numeri del secondo tipo che non appartengono al primo insieme. Ad esempio 9 è uno pseudoprimo di Eulero in base 17, ma non uno pseudoprimo di Eulero-Jacobi; mentre in base 19 è uno pseudoprimo di Eulero e di Eulero-Jacobi. Infatti:

( 17 ) ( 9 − 1 ) / 2 ≡ ( − 1 ) 4 = 1 mod 9 {\displaystyle (17)^{(9-1)/2}\equiv (-1)^{4}=1\mod 9}
( 17 ) ( 9 − 1 ) / 2 ≡ ( − 1 ) 4 = 1 ≠ − 1 = ( 17 9 ) mod 9 {\displaystyle (17)^{(9-1)/2}\equiv (-1)^{4}=1\neq -1=\left({\frac {17}{9}}\right)\mod 9}

Invece,

( 19 ) ( 9 − 1 ) / 2 ≡ ( 1 ) 4 = 1 mod 9 {\displaystyle (19)^{(9-1)/2}\equiv (1)^{4}=1\mod 9} .
( 19 ) ( 9 − 1 ) / 2 ≡ ( 1 ) 4 = 1 = 1 = ( 19 9 ) mod 9 {\displaystyle (19)^{(9-1)/2}\equiv (1)^{4}=1=1=\left({\frac {19}{9}}\right)\mod 9}

La differenza dei due casi (pseudoprimi di Eulero o di Eulero-Jacobi) si trova nella scelta di +1 o -1, che rende più raffinata la valutazione di Eulero-Jacobi.

Ogni pseudoprimo di Eulero è anche uno pseudoprimo di Fermat in base a, ma non vale il viceversa.

Esistono inoltre numeri che sono pseudoprimi di Eulero in ogni base a coprima con loro stessi; tali numeri sono detti pseudoprimi assoluti di Eulero. Questi numeri sono un sottoinsieme degli pseudoprimi assoluti di Fermat, generalmente chiamati numeri di Carmichael. Il più piccolo pseudoprimo assoluto di Eulero è 1729.

Voci correlate

  • Piccolo teorema di Fermat
  • Numero primo
  • Pseudoprimo
  • Pseudoprimo forte
  • Test di Wilson
  • Test di Lucas-Lehmer
  • Test di Miller-Rabin
  Portale Crittografia
  Portale Matematica