Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Critère d'Euler
Résumé
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.
Soient un nombre premier différent de 2 et un entier premier avec .
Si est un résidu quadratique modulo , alors .
Si n'est pas un résidu quadratique modulo alors .
Ce qui se résume, en utilisant le symbole de Legendre, par :
La preuve 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é.
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 = 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 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 = 28 ≡ 4 ≡ (–1) ≡ 1 (mod 17), donc 2 est un résidu quadratique.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.