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 et plus précisément en arithmétique modulaire un nombre pseudo-premier d'Euler désigne un nombre entier particulier.

Un nombre impair composé n est appelé un pseudo-premier d'Euler de base a, si a et n sont premiers entre eux, et

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

(égalité de congruence modulo n).

Cette définition est motivée par le fait que tous les nombres premiers p satisfont à la relation ci-dessus, ce qui peut être démontré à partir du petit théorème de Fermat. Le théorème de Fermat établit que si p est premier, et premier avec a, alors

a^{p-1} \equiv  1 \ (p).

Supposons que p > 2 soit premier, alors p peut être exprimé sous la forme 2q+1 où q est un entier. Ainsi

a^{(2q+1)-1} \equiv  1 \ (p)

ce qui veut dire que

a^{2q} - 1 \equiv 0 \ (p).

D'où en factorisant le premier membre

(a^{q} - 1)(a^{q} + 1) \equiv 0 \ (p)

ce qui est équivalent à

a^{(p-1)/2} \equiv \pm 1 \ (p) .

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 Carmichaël, le plus petit pseudo-premier absolu d'Euler est 1729 = 7×13×19.

Il devrait être noté que la condition plus forte

a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \ (n)

où pgcd(a,n)=1 et \left(\frac{a}{n}\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]