Lemme de Zolotarev

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, le lemme de Zolotarev est un résultat d'arithmétique modulaire énonce que le symbole de Legendre

$\left(\frac{a}{p}\right)$

pour un entier a modulo un nombre premier p, peut être calculé de la manière suivante:

ε(π_a)

avec ε désignant la signature d'une permutation et π_a la permutation de la classe des résidus mod p qui multiplie chaque élément par a, à condition que p ne divise pas a.

[modifier] Preuve

Un élément non nul a du corps fini à p éléments agit par multiplication à droite sur le groupe multiplicatif de ce corps. Il est facile de voir que cette action admet (p-1)/i orbites, chacune de taille i, où i est l'ordre de a (c'est-à-dire le plus petit entier tel que $a i = 1$ ). La signature de cette action est alors $\epsilon(\tau_a)=(-1)^{(i-1)\frac{p-1}{i}}$ .

On discute alors suivant la parité de i : si i est pair alors $\left (\frac{a}{p}\right)=a^{(p-1)/2}=(a^{i/2})^{(p-1)/i}=(-1)^{(p-1)/i}=\epsilon(\tau_a)$ ; si i est impair alors $\left (\frac{a}{p}\right)=a^{(p-1)/2}=(a^{i})^{(p-1)/2i}=1=\epsilon(\tau_a)$ . Dans les deux cas, c'est le résultat attendu.