Pseudoprimo di Eulero

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

$a^{\frac{n-1}{2}}\equiv \pm 1modn$

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}\equiv 1modp$

Se ora p>2, si ha

$a^{2\cdot \frac{p-1}{2}}\equiv 1modp$, ovvero $a^{\frac{p-1}{2}}\equiv \pm 1modp$

Una forma più forte della relazione precedente è

$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}\equiv (-1{)}^4=1mod9$

$(17{)}^{(9-1)/2}\equiv (-1{)}^4=1\ne -1=\left(\frac{17}{9}\right)mod9$

Invece,

$(19{)}^{(9-1)/2}\equiv (1{)}^4=1mod9$.

$(19{)}^{(9-1)/2}\equiv (1{)}^4=1=1=\left(\frac{19}{9}\right)mod9$

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