Symbole de legendre

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-Marie Legendre.

Définition

Le symbole de Legendre est un cas particulier du symbole de Jacobi. Sa définition est la suivante :

Si p est un nombre premier et a un entier, alors le symbole de Legendre $\left(\frac{a}{p}\right)$ vaut :

• 0 si p divise a
• 1 si a est un résidu quadratique modulo p (ce qui signifie qu'il existe un entier k tel que k² ≡ a (mod p))
• −1 si a n'est pas un résidu quadratique modulo p.

Propriétés du symbole de Legendre

Voici quelques propriétés du symbole de Legendre, utiles pour simplifier certains calculs :

Critère d'Euler

Il est également possible de formuler le critère d'Euler en utilisant le symbole de Legendre :

$\left(\frac{a}{p}\right) \equiv a^{\left(\frac{p-1}{2}\right)}\ \left({\bmod p}\right)$

En effet, on remarque dans un premier temps que p est un entier impair, donc (p - 1)/2 est un entier.

Si a est un multiple de p, alors il en est de même de a à la puissance (p - 1)/2 et les deux entiers sont congrus à 0 modulo p. Si a n'est pas un multiple de p, alors a et p sont premiers entre eux car p est premier.

Considérons l'application du groupe multiplicatif Z/pZ^* dans lui-même, qui à la classe de x associe la classe de x². C'est un morphisme de groupe d'image l'ensemble des résidus quadratique de Z/pZ et de noyau {-1, 1}. Le théorème de Lagrange montre que l'ensemble des résidus quadratiques est un sous-groupe de Z/pZ^* d'ordre (p - 1)/2. Dans Z/pZ^*, il existe donc exactement (p - 1)/2 résidus quadratiques et autant d'éléments qui ne le sont pas.

Considérons alors l'application φ du groupe multiplicatif Z/pZ^* dans lui-même, qui à la classe de x associe la classe de x à la puissance (p - 1)/2. C'est aussi un morphisme de groupe et le théorème de Lagrange démontre qu'il est à valeur dans {-1, 1}, c'est-à-dire dans les racines du polynôme formel X² - 1. Son noyau est donc d'ordre (p - 1)/2.

Si a est un résidu quadratique, alors, par définition, il existe un entier b tel que son carré est congru à a modulo p. Le théorème de Lagrange appliqué au groupe multiplicatif Z/pZ^* montre que b^{p -1} est congru à 1 modulo p, ce qui implique que a à la puissance (p - 1)/2 est congru à 1 modulo p. On en déduit que le noyau du morphisme φ est composé des résidus quadratiques de Z/pZ^*.

Réciproquement, si a n'est pas un résidu quadratique, il n'est pas dans le noyau de φ, en conséquence son image par φ est égal à la classe de -1, ce qui termine la démonstration.

Le critère d'Euler montre que l'application qui à a associe le symbole de Legendre pour les classes modulo p est un morphisme du groupe Z dans {-1, 1}, c'est donc un caractère de Dirichlet.

Lemme de Gauss

Article détaillé : Lemme de Gauss.

Soit $p \in \mathbb{N}$ premier. Alors $\forall a, \exists \tilde a, a \equiv \tilde a [p], -\frac{p+1}{2} < \tilde a \leq \frac{p-1}{2}$. L'énoncé du lemme est le suivant: si l désigne le nombre d'entiers négatifs dans $\{\tilde a, 2 \tilde a, ... \frac{p-1}{2}\tilde a\}$ et $a \not\equiv 0 [p]$, on a : $\left(\frac{a}{p}\right) = (-1)^l$

Autre formulation

Soit $p \in \mathbb{N}$ premier et soit (a,p) = 1. Considèrons les entiers $a, 2a, 3a, ... , \frac{p-1}{2}a$ et leurs plus petits résidus positifs modulo p. Soit n le nombre de ces résidus qui excèdent $\frac{p}{2}$. Alors, $\left(\frac{a}{p}\right) = (-1)^n$

Corollaires

1. $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ (le symbole de Legendre est donc une fonction complètement multiplicative par rapport à son argument supérieur).

En effet, $\left(\frac{ab}{p}\right) = (ab)^{\frac{p-1}{2}} = (a)^{\frac{p-1}{2}} (b)^{\frac{p-1}{2}} = \left(\frac{a}{p}\right).\left(\frac{b}{p}\right)$

1. Si a ≡ b (mod p), alors $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
2. $\left(\frac{1}{p}\right) = 1$ car 1 est le carré de lui-même
3. $\left(\frac{-1}{p}\right) = (-1)^{\left(\frac{p-1}{2}\right)} = \left\{ \begin{matrix} {1 \mbox{ si } p \equiv 1 [4] } \\ {-1 \mbox{ si } p \equiv 3 [4]} \end{matrix} \right.$. Ceci est une conséquence directe du critère d'Euler.
4. $\left(\frac{2}{p}\right) = (-1)^{\left(\frac{p^2-1}{8}\right)}$ = 1 si p ≡ 1 ou 7 (mod 8) et −1 si p ≡ 3 ou 5 (mod 8)
5. $\left(\frac{a}{2}\right)$ = 1 si a est impair et 0 sinon
6. Si q est un nombre premier impair alors $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}$

La dernière propriété est connue sous le nom de loi de réciprocité quadratique.

Généralisation du symbole de Legendre

Article détaillé : Symbole de Jacobi.

Le symbole de Jacobi est une généralisation du symbole de Legendre. Avec le symbole de Legendre $\left(\frac{a}{b}\right)$, l'entier b est nécessairement premier ; en revanche, le symbole de Jacobi permet de considérer le cas où b est un nombre composé ($\left(\frac{2}{6}\right)$ par exemple).

Analyse harmonique sur Z/pZ^*

Article détaillé : Analyse harmonique sur un groupe abélien fini.

Le caractère multiplicatif du symbole de Legendre montre qu'il est un caractère du groupe multiplicatif Z/pZ^*. Cette remarque rend possible l'utilisation des outils de l'analyse harmonique sur un groupe fini. Ces outils sont à la source de nombreuses démonstration en arithmétique. On peut citer par exemple le calcul des sommes ou des périodes de Gauss ce qui permet une démonstration de la loi de réciprocité quadratique.

Ce document provient de « Symbole de Legendre ».