Nombre pseudo-premier d'Euler

Cet article ne cite pas suffisamment ses sources (février 2018).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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^[1] 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 a, 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^[2]. 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).