critère d’Euler

ARITHMETIQUE

Le critère d’Euler est un résultat de théorie des nombres qui permet de déterminer si un entier donné est un résidu quadratique modulo un nombre premier.

Définition préalable : a est un résidu quadratique modulo p signifie : il existe un entier k tel que k² ≡ a (mod p).

Enoncé du critère d’Euler :
1. si a est un résidu quadratique modulo p, alors a^(p-1)/2 ≡ 1 (mod p)
2. si a n’est pas un résidu quadratique modulo p, alors a^(p-1)/2 ≡ -1 (mod p).

Le critère d’Euler peut être généralisé aux résidus n-ièmes (voir http://lipn.univ-paris13.fr/~banderier/Recipro/node13.html )
Les nombres qui vérifient le test de primalité associé au critère d’Euler sont appelés pseudo-premier d’Euler . Ceux d’entre eux qui sont composés sont pseudo-premiers d’Euler-Jacobi .