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 :

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 où pgcd(a, n) = 1 et 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

modifier
(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).
  1. Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions].
  2. https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

Voir aussi

modifier

Article connexe

modifier

Nombre premier probable

Lien externe

modifier

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