Nombre pseudo-premier d'Euler

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Nombre pseudopremier d'Euler)
Aller à : navigation, rechercher

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 a, cette congruence a lieu.

La relation peut être vérifiée plutôt 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.

Chaque pseudo-premier d'Euler est aussi un 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 à elles-mêmes. Les pseudo-premiers absolus d'Euler sont 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 an\right) \pmod n où pgcd(a, n) = 1 et \left(\frac an\right) est le symbole de Jacobi, est quelquefois utilisée pour une définition d'un pseudo-premier d'Euler. Une discussion sur les nombres de cette forme peut être trouvée sur l'article « Nombre pseudo-premier d'Euler-Jacobi ».

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Nombre premier probable

Lien externe[modifier | modifier le code]

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


(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).