Nombre pseudo-premier d'Euler

En mathématiques, un nombre pseudo-premier d'Euler de base a est un nombre composé impair n premier avec a et tel que la congruence suivante soit vérifiée :

$a^{(n-1)/2}\equiv \pm 1{\pmod {n}}.$

Cette définition est motivée par le critère d'Euler (qui précise le petit théorème de Fermat), d'après lequel si n est un nombre premier impair premier avec n, cette congruence a lieu.

La relation peut être vérifiée assez rapidement, ce qui est utilisé pour les tests de primalité. Ces tests sont deux fois plus forts que les tests basés sur le petit théorème de Fermat.

Tout nombre pseudo-premier d'Euler est aussi un nombre pseudo-premier de Fermat. Il n'est pas possible de produire un test définitif de primalité basé sur l'éventualité qu'un nombre soit un pseudo-premier d'Euler parce qu'il existe des nombres pseudo-premiers absolus d'Euler, qui sont des pseudo-premiers d'Euler pour chaque base relativement première à eux-mêmes. Les nombres pseudo-premiers absolus d'Euler forment un sous-ensemble des pseudo-premiers de Fermat absolus, ou nombres de Carmichael. Le plus petit pseudo-premier absolu d'Euler est 1729 = 7 × 13 × 19.

La condition plus forte $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ où pgcd(a, n) = 1 et $\left({\frac {a}{n}}\right)$ est le symbole de Jacobi, est quelquefois prise comme définition d'un pseudo-premier d'Euler. Une discussion sur les nombres de cette forme peut être trouvée dans l'article « Nombre pseudo-premier d'Euler-Jacobi ».

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Euler pseudoprime » (voir la liste des auteurs).

Voir aussi

Article connexe

Nombre premier probable

Lien externe

Nombres pseudo-premiers d'Euler de base 2 : suite A006970 de l'OEIS