Concept

Gauss's lemma (number theory)

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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related lectures (10)
Radiation and Antennas: System Aspects
Explores radiation and antennas, covering power balance, transmission parameters, and practical examples of antenna concepts.
Polynomes: Irreducible Polynomials and Gaussian Lemma
Introduces irreducible polynomials and the Gaussian lemma for polynomial factorization.
Gaussian Lemma III: Irreducibility and Primitive Polynomials
Explains irreducibility in polynomial equations and the properties of primitive polynomials.
Show more
Related publications (5)

Bioconversion of sugarcane crop residue for value added products - An overview

Edgard Gnansounou

Sugarcane is a major crop cultivated globally and the residue left over after the crop harvest and extraction of juice is a good biomass source that can be used for the production of several useful chemicals. The sugarcane bagasse is an excellent substrate ...
Pergamon-Elsevier Science Ltd2016

Bioconversion of sugarcane crop residue for value added products - An overview

Edgard Gnansounou

Sugarcane is a major crop cultivated globally and the residue left over after the crop harvest and extraction of juice is a good biomass source that can be used for the production of several useful chemicals. The sugarcane bagasse is an excellent substrate ...
Elsevier2016

Comparative Evaluation of Three Sugarcane Supply Strategies in Colombia: Logistics, Energy and GHG Emissions

François Maréchal, Jairo Alexander Lozano Moreno

Sugarcane-based ethanol in Colombia has a prospective opportunity to explore the production of ethanol from lignocellulosic biomass taking into account that a large amount of generated residues (between 50 and 100 t/ha) are left on the field after green ha ...
2015
Show more
Related concepts (6)
Quartic reciprocity
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x4 ≡ p (mod q) to that of x4 ≡ q (mod p). Euler made the first conjectures about biquadratic reciprocity. Gauss published two monographs on biquadratic reciprocity.
Quadratic residue
In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.
Legendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0. The Legendre symbol was introduced by Adrien-Marie Legendre in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.