Critère d'Euler

Critère d'Euler

En mathématiques et plus précisément en arithmétique modulaire, le critère d'Euler est utilisé en théorie des nombres pour déterminer si un entier donné est un résidu quadratique modulo un nombre premier.

Définition

Considérons un nombre premier p différent de 2 et un entier a premier avec p ; alors le critère d'Euler s'énonce de la façon suivante :

  1. si a est un résidu quadratique modulo p (c'est-à-dire s'il existe un entier k tel que k2a (mod p)), alors a^{\frac{p-1}2} \equiv 1 \pmod p
  2. si a n'est pas un résidu quadratique modulo p alors a^{\frac{p-1}2} \equiv -1 \pmod p,

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


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

Démonstration du critère d'Euler

Considérons les p-1 éléments non nuls de l'anneau Z/pZ.

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

Xp − 1 − 1 = (X(p − 1) / 2 − 1)(X(p − 1) / 2 + 1),

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 (X2)(p − 1) / 2 − 1 = Xp − 1 − 1).

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

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.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Critère d'Euler de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Critere d'Euler — Critère d Euler En mathématiques et plus précisément en arithmétique modulaire, le critère d Euler est utilisé en théorie des nombres pour déterminer si un entier donné est un résidu quadratique modulo un nombre premier. Définition Considérons un …   Wikipédia en Français

  • Critère — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Un critère (du grec kriterion, de krinein, juger) est un principe auquel on se réfère, ou un moyen qu on utilise, pour établir un jugement. Cette notion… …   Wikipédia en Français

  • Liste des sujets nommés d'après Leonhard Euler — En mathématiques et en physique, il existe un grand nombre de sujets nommés en l honneur de Leonhard Euler, dont beaucoup sont désignés par leur rôle : équation, formule, identité, nombre (unique ou séquence) ou une autre entité… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Symbole de Legendre — Le symbole de Legendre est une notation utilisée par les mathématiciens, en théorie des nombres, particulièrement dans les domaines de la factorisation et des résidus quadratiques. Il est nommé ainsi en l honneur du mathématicien français Adrien… …   Wikipédia en Français

  • Symbole de legendre — Le symbole de Legendre est une notation utilisée par les mathématiciens, en théorie des nombres, particulièrement dans les domaines de la factorisation et des résidus quadratiques. Il est nommé ainsi en l honneur du mathématicien français Adrien… …   Wikipédia en Français

  • DIVISIBILITÉ — L’étude élémentaire de la divisibilité dans l’anneau Z des entiers relatifs résulte de l’existence de la division euclidienne qui entraîne que cet anneau est principal. Les propriétés générales des anneaux principaux sont exposées dans l’article… …   Encyclopédie Universelle

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”