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 <math>p</math> un nombre premier différent de 2 et <math>a</math> un entier premier avec <math>p</math>.

• Si <math>a</math> est un résidu quadratique modulo <math>p</math><ref>C'est-à-dire s'il existe un entier <math>k</math> tel que <math>a\equiv k^2\pmod p</math>.</ref>, alors <math>a^{\frac{p-1}2} \equiv1\pmod p</math>.
• Si <math>a</math> n'est pas un résidu quadratique modulo <math>p</math> alors <math>a^{\frac{p-1}2}\equiv-1\pmod p</math>.

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

<math>

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

</math>.

La preuve<ref>Voir par exemple Modèle:Ouvrage ou Modèle:Note autre projet</ref> 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é<ref>Euler utilise ici sa méthode des différences finies comme dans sa preuve du théorème des deux carrés, car il ne savait pas encore que modulo un nombre premier, une congruence de degré r a au plus r solutions. Lagrange le lui fit remarquer fin 1770-début 1771. Modèle:Weil1, Modèle:P..</ref>.

Exemples

Soit Modèle:Mvar = 17. Modulo quels nombres premiers Modèle:Mvar (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 Modèle:Mvar à 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²)Modèle:3 ≡ 3Modèle: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 Modèle:Mvar > 2, (17/Modèle:Mvar) = 1 si et seulement si, modulo 17, Modèle:Mvar 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<ref>Modèle:Article (E262, écrit en 1755 et présenté en 1758).</ref> est en réalité plus général : Modèle:Énoncé

La preuve<ref>Voir par exemple Modèle:Note autre projet</ref> utilise les mêmes arguments que dans le cas n = 2 Modèle:Supra. Euler redémontre au préalable<ref>Par un raisonnement qui — à une époque où la notion de groupe n'avait pas encore émergé — préfigure le théorème de Lagrange sur les groupes.</ref> le petit théorème de Fermat (le cas Modèle:Mvar = 1). Il remarque par ailleurs que pour tout entier Modèle:Mvar, si r² ≡ 1 mod p alors r ≡ ±1 mod p<ref>Si p divise r² – 1 = (r + 1)(r – 1), il divise l'un des deux facteurs.</ref>. Appliquée à Modèle:Nobr (pour p ≠ 2), cette remarque complète son critère dans le cas Modèle:Mvar = 2 : si <math>a</math> n'est pas un carré mod Modèle:Mvar, non seulement r n'est pas congru à 1, mais il est congru à –1.

Articles connexes

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