Legendre Symbol
The Legendre symbol is a notation used for stating a central theorem of elementary number theory, the quadratic reciprocity law. This theorem was first proved by Carl Friedrich Gauss in 1801, after the French mathematician Adrien-Marie Legendre had published two incorrect proofs. As a sort of consolation prize, tradition has named the notation after Legendre.
The quadratic reciprocity law gives an effective procedure for determining whether a number is a perfect square in modular arithmetic. For example, 2 is a square modulo 7, because it is congruent to the number 9 = 3^*2. By contrast, 3 is not a square modulo 7. It is congruent to the numbers 10, 17, 24, 31,..., none of which is the square of a whole number.
In the real number system, it is easy to tell squares and non-squares apart. Squares are positive or zero, and non-squares are negative. But it is much less obvious how to tell whether a number x is a square (modulo n). As a first step, it turns out to be sufficient to determine whether xx is a square modulo each of the prime factors of n. If so, then it is also a square modulo n.
Hence the key problem is to determine when x is a square modulo a prime number p. This is where the Legendre symbol enters the problem. The Legendre symbol, written (x/p), is defined as follows: (x/p) = 1 if x is a square modulo p, and (x/p) = -1 if x is not a square modulo p. Note that the parentheses are an essential part of the symbol, and that the Legendre symbol (x/p) has nothing to do, in general, with the fraction x/p. For example, (2/7) = 1 and (3/7) = -1.
The Legendre symbol possesses some algebraic properties that make it a useful device for solving the "key problem" mentioned above. First, it is multiplicative: (xy/p) = (x/p)( y/p). Stated in words, this means: a square times a non-square is a square; a square times a non-square is a non-square; and a non-square times a non-square is a square. (Compare this with the arithmetic of positive and negative numbers.) Second, the Legendre symbol satisfies the law of quadratic reciprocity. Assuming that both x and p are odd primes, their roles can be reversed. More specifically, (x/p) = (p/x) if either x or p is 1 greater than a multiple of 4; but if x and p are both 3 greater than a multiple of 4, then (x/p) = -(p/x).
As an example, to compute (3/7), we switch the 3 and 7. Noting that 3 and 7 are both 3 greater than a multiple of 4, we conclude that (3/7) = -(7/3). But since 7 is congruent to 1 modulo 3, and 1 is a square (1 = 12), 7 is also a square, and hence (7/3) = 1. This means (3/7) = -1, so 3 is not a square modulo 7.
There is no truly simple explanation for why quadratic reciprocity works; Gauss himself proved it six times, looking for a more satisfying answer. But quadratic reciprocity and its generalizations have led to many deep results in number theory, including Dirichlet's theorem on primes in arithmetic progressions; factoring techniques such as the "quadratic sieve"; and the entire field of algebraic number theory. Legendre symbols themselves provide the most basic example of a multiplicative function from a group (here, the numbers modulo pp) into the real numbers. Such functions are now called characters, and play a fundamental role in both number theory and group theory.
This is the complete article, containing 589 words
(approx. 2 pages at 300 words per page).
