Critère d'Euler

En mathématiques et plus précisément en arithmétique modulaire, le critère d'Euler est un théorème utilisé en théorie des nombres pour déterminer si un entier donné est un résidu quadratique (autrement dit, un carré) modulo un nombre premier.

Énoncé

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].

Exemples

Exemple 1 : trouver les nombres premiers modulo lesquels a est un carré^{[non pertinent]}

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.

Généralisation

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.