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 un nombre premier différent de 2 et un entier premier avec . Si est un résidu quadratique modulo C'est-à-dire s'il existe un entier tel que ., alors . Si n'est pas un résidu quadratique modulo alors .
Ce qui se résume, en utilisant le symbole de Legendre, par :
.
La preuveVoir par exemple ou 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é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. , ..
Exemples Exemple 1 : trouver des nombres premiers p pour lesquels a est un carré modulo p
Soit = 17. Modulo quels nombres premiers (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 à la demande. Par exemple : modulo 3, on a 17(3 − 1)/2 = 171 ≡ −1 ; par conséquent, 17 n'est pas un carré modulo 3. modulo 13, on a 17(13 − 1)/2 ≡ 46 = (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 > 2, (17/) = 1 si et seulement si, modulo 17, 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; autrement dit : 1, 2, 4, 8, 9, 13, 15 et 16 (il y en a donc bien (p-1)/2 = (17-1)/2 = 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 = 28 ≡ 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 = 38 ≡ (–8) ≡ (–4) ≡ −1 (mod 17), donc 3 n'est pas un résidu quadratique.
Généralisation Le critère énoncé par Euler (E262, écrit en 1755 et présenté en 1758). est en réalité plus général :
La preuveVoir par exemple utilise les mêmes arguments que dans le cas n = 2 . Euler redémontre au préalablePar 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. le petit théorème de Fermat (le cas = 1). Il remarque par ailleurs que pour tout entier , si r ≡ 1 mod p alors r ≡ ±1 mod pSi p divise r – 1 = (r + 1)(r – 1), il divise l'un des deux facteurs.. Appliquée à (pour p ≠ 2), cette remarque complète son critère dans le cas = 2 : si n'est pas un carré mod , non seulement r n'est pas congru à 1, mais il est congru à –1.
Notes et références
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
Catégorie:Théorème de la théorie des nombres Catégorie:Arithmétique modulaire Catégorie:Leonhard Euler