Critère d'Euler

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 modulo un nombre premier.

Énoncé[modifier | modifier le code]

Soient p un nombre premier différent de 2 et a un entier premier avec p.

  • Si a est un résidu quadratique modulo p (c'est-à-dire s'il existe un entier k tel que k2a (mod p)), alors .
  • Si a n'est pas un résidu quadratique modulo p alors [1].

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

Démonstration[modifier | modifier le code]

Considérons les p − 1 éléments non nuls de l'anneau ℤ/p.

D'après le petit théorème de Fermat, tous sont racines du polynôme

,

or sur un anneau intègre, un polynôme n'a jamais plus de racines que son degré.

Parmi ces p − 1 éléments, il y en a donc exactement (p − 1)/2 qui vérifient x(p−1)/2 = 1, et autant qui vérifient x(p−1)/2 = −1.

De plus, tous les carrés font partie du premier lot (car ).

Enfin, les carrés sont au nombre de (p − 1)/2 (car chaque carré est le carré d'exactement deux éléments, opposés l'un de l'autre), donc constituent la totalité du premier lot.

Exemples[modifier | modifier le code]

Exemple 1 : Trouver les nombres premiers pour lesquels a est un résidu

Soit a = 17. Pour quels nombres premiers p, 17 est-il un résidu quadratique ?

Nous pouvons tester les nombres premiers p' donnés manuellement par la formule précédente.

Dans un cas, testons p = 3, nous avons 17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ −1 (mod 3), par conséquent 17 n'est pas un résidu quadratique modulo 3.

Dans un autre cas, testons p = 13, nous avons 17(13 − 1)/2 = 176 ≡ 1 (mod 13), par conséquent 17 est un résidu quadratique modulo 13. Comme confirmation, 17 ≡ 4 (mod 13) et 22 = 4.

Nous pouvons faire ces calculs plus rapidement en utilisant l'arithmétique modulaire et les propriétés du symbole de Legendre.

Si nous calculons les valeurs, nous trouvons :

(17/p) = +1 pour p = {13, 19, ...} (17 est un résidu quadratique modulo ces valeurs)
(17/p) = −1 pour p = {3, 5, 7, 11, 23, ...} (17 n'est pas un résidu quadratique modulo ces valeurs)

Exemple 2 : Trouver les résidus avec un module premier p donné.

Quels nombres sont les carrés modulo 17 (résidus quadratiques modulo 17) ?

Nous pouvons calculer manuellement :

12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17)

Donc, l'ensemble des résidus quadratiques modulo 17 est {1,2,4,8,9,13,15,16}. Notez que nous n'avons pas besoin de calculer les carrés pour les valeurs de 9 à 16, comme elles sont toutes négatives par rapport à la valeurs carrée précédente (c.a.d. 9 ≡ −8 (mod 17), donc 92 = (−8)2 = 64 ≡ 13 (mod 17)).

Nous pouvons trouver les résidus quadratique ou les vérifier en utilisant la formule précédente. Pour tester si 2 est un résidu quadratique modulo 17, nous calculons 2(17 − 1)/2 = 28 ≡ 1 (mod 17), donc elle est un résidu quadratique. Pour tester si 3 est un résidu quadratique modulo 17, nous calculons 3(17 − 1)/2 = 38 = 16 ≡ −1 (mod 17) donc, il n'est pas un résidu quadratique.

Le critère d'Euler est relié à la loi de réciprocité quadratique et est utilisé dans la définition des nombres pseudo-premiers d'Euler-Jacobi.

Généralisation[modifier | modifier le code]

Le critère énoncé par Euler[2] 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) am ≡ 1 mod p.

Euler redémontre au préalable[4] le petit théorème de Fermat (le cas n = 1). Il remarque par ailleurs que pour tout entier r, si r2 ≡ 1 mod p alors r ≡ ±1 mod p[5]. Appliquée à r = a(p – 1)/2 (pour p ≠ 2), cette remarque complète son critère dans le cas n = 2 : si 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[modifier | modifier le code]

(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. (en) William J. LeVeque (en), Fundamentals of Number Theory, Dover, (1re éd. 1977) (lire en ligne), p. 68-69.
  2. (la) L. Euler, « Theoremata circa residua ex divisione potestatum relicta », Novi Comment. Acad. Sci. Imp. Petrop., vol. 7,‎ , p. 49-82 (lire en ligne) (E262, écrit en 1755 et présenté en 1758).
  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. 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.
  5. Si p divise r2 – 1 = (r + 1)(r – 1), il divise l'un des deux facteurs.

Article connexe[modifier | modifier le code]

Niveau d'un corps fini