Critère d'Euler

Soient ${\displaystyle p}$ un nombre premier différent de 2 et ${\displaystyle a}$ un entier premier avec ${\displaystyle p}$.

• Si ${\displaystyle a}$ est un résidu quadratique modulo ${\displaystyle p}$[1], alors ${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$.
• Si ${\displaystyle a}$ n'est pas un résidu quadratique modulo ${\displaystyle p}$ alors ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

Ce qui se résume, en utilisant le symbole de Legendre, par :

${\displaystyle a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}$.

La preuve[2] repose sur le petit théorème de Fermat et sur le fait que dans un anneau intègre, un polynôme n'a jamais plus de racines que son degré[3].

Exemple 1 : Trouver les nombres premiers modulo lesquels a est un carré

Soit a = 17. Modulo quels nombres premiers p (différents de 2 et 17) ce nombre 17 est-il un carré ?

On peut tester, par la formule précédente, des nombres premiers p à la demande. Par exemple :

• modulo 3, on a 17^{(3 − 1)/2} = 17¹ ≡ −1 ; par conséquent, 17 n'est pas un carré modulo 3.
• modulo 13, on a 17^{(13 − 1)/2} ≡ 4⁶ = (4²)³ ≡ 3³ ≡ 1 ; par conséquent, 17 est un carré modulo 13.

Cependant :

• on peut faire ces calculs bien plus rapidement en utilisant l'arithmétique modulaire :
  • modulo 3, 17 ≡ −1 n'est pas un carré, le seul carré non nul étant (±1)² = 1,
  • modulo 13, 17 ≡ 4 = 2² ;
• pour une réponse complète, il faut faire appel à la loi de réciprocité quadratique : pour un nombre premier p > 2, (17/p) = 1 si et seulement si, modulo 17, p est congru à ±1, ±2, ±4 ou ±8. Ainsi :
  • 17 est un carré modulo 13, 19, 43, 47, …
  • 17 n'est pas un carré modulo 3, 5, 7, 11, 23, …

Exemple 2 : Trouver les carrés modulo un nombre premier p donné.

Quels sont les carrés modulo 17 ?

On peut les calculer :

(±1)² = 1

(±2)² = 4

(±3)² ≡ –8 (mod 17)

(±4)² ≡ –1 (mod 17)

(±5)² ≡ 8 (mod 17)

(±6)² ≡ 2 (mod 17)

(±7)² ≡ –2 (mod 17)

(±8)² ≡ –4 (mod 17)

Donc les 8 carrés non nuls modulo 17 sont ±1, ±2, ±4, et ±8.

Pour savoir si un nombre est résidu quadratique, on peut regarder s'il est (modulo 17) dans la liste, ou le tester par le critère d'Euler. Pour tester si 2 est un carré modulo 17, on calcule 2^{(17 − 1)/2} = 2⁸ ≡ 4⁴ ≡ (–1)² ≡ 1 (mod 17), donc 2 est un résidu quadratique. Pour tester si 3 est un carré modulo 17, on calcule 3^{(17 − 1)/2} = 3⁸ ≡ (–8)⁴ ≡ (–4)² ≡ −1 (mod 17), donc 3 n'est pas un résidu quadratique.

Le critère énoncé par Euler[4] est en réalité plus général :

Soit p = 1 + mn un nombre premier. Un entier a non divisible par p est une puissance n-ième mod p si (et seulement si) a^m ≡ 1 mod p.

La preuve[5] utilise les mêmes arguments que dans le cas n = 2 (voir supra). Euler redémontre au préalable[6] le petit théorème de Fermat (le cas n = 1). Il remarque par ailleurs que pour tout entier r, si r² ≡ 1 mod p alors r ≡ ±1 mod p[7]. Appliquée à r = a^{(p – 1)/2} (pour p ≠ 2), cette remarque complète son critère dans le cas n = 2 : si ${\displaystyle a}$ n'est pas un carré mod p, non seulement r n'est pas congru à 1, mais il est congru à –1.

• Le critère d'Euler est utilisé dans la définition des nombres pseudo-premiers d'Euler-Jacobi.
• Niveau d'un corps fini