Ê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 GraphSearch.
Concept
Lemme de Gauss (théorie des nombres)
Résumé
Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.
It made its first appearance in Carl Friedrich Gauss's third proof (1808) of quadratic reciprocity and he proved it again in his fifth proof (1818).
For any odd prime p let a be an integer that is coprime to p.
Consider the integers
and their least positive residues modulo p. These residues are all distinct, so there are (p − 1)/2 of them.
Let n be the number of these residues that are greater than p/2. Then
where is the Legendre symbol.
Taking p = 11 and a = 7, the relevant sequence of integers is
7, 14, 21, 28, 35.
After reduction modulo 11, this sequence becomes
7, 3, 10, 6, 2.
Three of these integers are larger than 11/2 (namely 6, 7 and 10), so n = 3. Correspondingly Gauss's lemma predicts that
This is indeed correct, because 7 is not a quadratic residue modulo 11.
The above sequence of residues
7, 3, 10, 6, 2
may also be written
−4, 3, −1, −5, 2.
In this form, the integers larger than 11/2 appear as negative numbers. It is also apparent that the absolute values of the residues are a permutation of the residues
1, 2, 3, 4, 5.
A fairly simple proof, reminiscent of one of the simplest proofs of Fermat's little theorem, can be obtained by evaluating the product
modulo p in two different ways. On one hand it is equal to
The second evaluation takes more work. If x is a nonzero residue modulo p, let us define the "absolute value" of x to be
Since n counts those multiples ka which are in the latter range, and since for those multiples, −ka is in the first range, we have
Now observe that the values |ra| are distinct for r = 1, 2, ..., (p − 1)/2. Indeed, we have
because a is coprime to p.
This gives r = s, since r and s are positive least residues. But there are exactly (p − 1)/2 of them, so their values are a rearrangement of the integers 1, 2, ..., (p − 1)/2.
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.