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 ≡ −1 ; par conséquent, 17 n'est pas un carré modulo 3.
• modulo 13, on a 17^(13 − 1)/2 ≡ 4^6 = (4^2)^3 ≡ 3^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)^2 = 1,
  • modulo 13, 17 ≡ 4 = 2^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)^2 = 1

(±2)^2 = 4

(±3)^2 ≡ –8 (mod 17)

(±4)^2 ≡ –1 (mod 17)

(±5)^2 ≡ 8 (mod 17)

(±6)^2 ≡ 2 (mod 17)

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

(±8)^2 ≡ –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^8 ≡ 4^4 ≡ (–1)^2 ≡ 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 ≡ (–8)^4 ≡ (–4)^2 ≡ −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^2 ≡ 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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Euler's criterion » (voir la liste des auteurs).

1. C'est-à-dire s'il existe un entier ${\displaystyle k}$ tel que ${\displaystyle a\equiv k^{2}{\pmod {p}}}$.
2. Voir par exemple (en) William J. LeVeque, Fundamentals of Number Theory, Dover, 1996 (1^re éd. 1977) (lire en ligne), p. 68-69 ou « Critère d'Euler » dans la leçon « Introduction à la théorie des nombres » sur Wikiversité.
3. 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. (en) André Weil, Number Theory : An approach through history from Hammurapi to Legendre [détail des éditions], p. 198.
4. (la) L. Euler, « Theoremata circa residua ex divisione potestatum relicta », Novi Comment. Acad. Sci. Imp. Petrop., vol. 7,‎ 1761, p. 49-82 (lire en ligne) (E262, écrit en 1755 et présenté en 1758).
5. Voir par exemple cet exercice corrigé de la leçon « Introduction à la théorie des nombres » sur Wikiversité.
6. 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.
7. Si p divise r^2 – 1 = (r + 1)(r – 1), il divise l'un des deux facteurs.

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