Nombre pseudopremier d'Euler

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques et plus précisément en arithmétique modulaire un nombre pseudopremier d'Euler désigne un nombre entier particulier.

Un nombre impair composé n est appelé un pseudopremier 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 pseudopremier d'Euler est aussi un pseudopremier de Fermat. Il n'est pas possible de produire un test définitif de primalité basé sur l'éventualité qu'un nombre soit un pseudopremier d'Euler parce qu'il existe des nombres pseudopremiers absolus d'Euler, qui sont des pseudopremiers d'Euler pour chaque base relativement première à elles-mêmes. Les pseudopremiers absolus d'Euler sont un sous-ensemble des pseudopremiers de Fermat absolus, ou nombres de Carmichaël, le plus petit pseudopremier 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 quelque fois utilisée pour une définition d'un pseudopremier d'Euler. Une discussion sur les nombres de cette forme peut être trouvée sur l'article nombre pseudopremier d'Euler-Jacobi.