Legendre symbol

From Wikipedia
Jump to navigation Jump to search
Legendre symbol (a/p)
for various a (along top) and p (along left side).
a
p
0 1 2 3 4 5 6 7 8 9 10 11 12
3 0 1 −1
5 0 1 −1 −1 1
7 0 1 1 −1 1 −1 −1
11 −0 −1 −1 1 −1 1 −1 −1 −1 −1 −1
13 −0 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1

Only 0 ≤ a < p are shown, since due to the first property below any other a can be reduced modulo p. Quadratic residues are highlighted in yellow, and correspond precisely to the values 0 and 1.

In number theory, the Legendre symbol is a function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0\pmod p, \\ -1 & \text{if } a \text{ is a quadratic nonresidue modulo } p, \\ 0 & \text{if } a \equiv 0 \pmod p. \end{cases}}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is an odd prime number and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} is a positive integer that may or may not be a quadratic residue mod p. The Legendre symbol is a multiplicative function

The Legendre symbol was introduced by Adrien-Marie Legendre in 1797 or 1798[1] 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. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol.

Definition

Legendre's original definition was by means of the explicit formula

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \quad \text{ and } \quad\left(\frac{a}{p}\right) \in \{-1,0,1\}. }

By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent.[2] Thus Legendre's contribution lay in introducing a convenient notation that recorded quadratic residuosity of a mod p. For the sake of comparison, Gauss used the notation aRp, aNp according to whether a is a residue or a non-residue modulo p. For typographical convenience, the Legendre symbol is sometimes written as (a | p) or (a/p). For fixed p, the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\tfrac{0}{p}\right),\left(\tfrac{1}{p}\right),\left(\tfrac{2}{p}\right),\ldots} is periodic with period p and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.

Properties of the Legendre symbol

There are a number of useful properties of the Legendre symbol which, together with the law of quadratic reciprocity, can be used to compute it efficiently.

  • Given a generator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \in \mathbb{F}_p^*} , if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = g^r} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is a quadratic residue if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} is even. This shows that half of the elements in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_p^*} are quadratic residues.
  • If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \equiv 3 \text{ mod } 4} then the fact that
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{p+1}{4} + \frac{p+1}{4} = \frac{p+1}2 = \frac{(p-1)+2}{2} = \frac{p-1}2 + 1} gives us that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = x^{(p+1)/4}} is a square root of the quadratic residue Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .
  • The Legendre symbol is periodic in its first (or top) argument: if a ≡ b (mod p), then
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).}
  • The Legendre symbol is a completely multiplicative function of its top argument:
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).}
  • In particular, the product of two numbers that are both quadratic residues or quadratic non-residues modulo p is a residue, whereas the product of a residue with a non-residue is a non-residue. A special case is the Legendre symbol of a square:
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{x^2}{p}\right) = \begin{cases} 1 & \mbox{if }p\nmid x\\ 0 & \mbox{if }p\mid x. \end{cases}}
  • When viewed as a function of a, the Legendre symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) } is the unique quadratic (or order 2) Dirichlet character modulo p.
  • The first supplement to the law of quadratic reciprocity:
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & \mbox{ if }p \equiv 1\pmod{4} \\ -1 & \mbox{ if }p \equiv 3\pmod{4}. \end{cases}}
  • The second supplement to the law of quadratic reciprocity:
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{2}{p}\right) = (-1)^\tfrac{p^2-1}{8} = \begin{cases} 1 & \mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\ -1 & \mbox{ if }p \equiv 3\mbox{ or }5 \pmod{8}. \end{cases}}
  • Special formulas for the Legendre symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) } for small values of a:
    • For an odd prime p ≠ 3,
      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} = \begin{cases} 1 & \mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\ -1 & \mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12}. \end{cases}}
    • For an odd prime p ≠ 5,
      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{2p+2}{5}\big \rfloor} = \begin{cases} 1 & \mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\ -1 & \mbox{ if }p \equiv 2\mbox{ or }3 \pmod5. \end{cases}}
  • The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... are defined by the recurrence F1 = F2 = 1, Fn+1 = Fn + Fn−1. If p is a prime number then
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p. }
For example,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left(\tfrac{2}{5}\right) &= -1, & F_3 &= 2, & F_2 &= 1, \\ \left(\tfrac{3}{5}\right) &= -1, & F_4 &= 3, & F_3 &= 2, \\ \left(\tfrac{5}{5}\right) &= 0, & F_5 &= 5, & & \\ \left(\tfrac{7}{5}\right) &= -1, & F_8 &= 21, & F_7 &= 13, \\ \left(\tfrac{11}{5}\right) &= 1, & F_{10} &= 55, & F_{11} &= 89. \end{align}}

Sums of Legendre symbols

Sums of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum \left(\frac{f\left(a \right) }{p}\right)} , typically taken over all integers in the range Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[0,p-1\right]} for some function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , are a special case of character sums. They are of interest in the distribution of quadratic residues modulo a prime number.

Legendre symbol and quadratic reciprocity

Let p and q be distinct odd primes. Using the Legendre symbol, the quadratic reciprocity law can be stated concisely:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}}.}

Many proofs of quadratic reciprocity are based on Euler's criterion

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.}

In addition, several alternative expressions for the Legendre symbol were devised in order to produce various proofs of the quadratic reciprocity law.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^{p-1}\zeta^{ak^2}=\left(\frac{a}{p}\right)\sum_{k=0}^{p-1}\zeta^{k^2},\qquad \zeta = e^{\frac{2\pi i}{p}}}
in his fourth[4] and sixth[5] proofs of quadratic reciprocity.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{p}{q}\right) =\sgn\left(\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)\right).}
Reversing the roles of p and q, he obtains the relation between (p/q) and (q/p).
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{q}{p}\right) =\prod_{n=1}^{\frac{p-1}{2}} \frac{\sin\left(\frac{2\pi qn}{p}\right)}{\sin\left(\frac{2\pi n}{p}\right)}.}
Using certain elliptic functions instead of the sine function, Eisenstein was able to prove cubic and quartic reciprocity as well.
  • The Jacobi symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{n}\right)} is a generalization of the Legendre symbol that allows for a composite second (bottom) argument n, although n must still be odd and positive. This generalization provides an efficient way to compute all Legendre symbols without performing factorization along the way.
  • A further extension is the Kronecker symbol, in which the bottom argument may be any integer.
  • The power residue symbol (a/n)n generalizes the Legendre symbol to higher power n. The Legendre symbol represents the power residue symbol for n = 2.

Computational example

The above properties, including the law of quadratic reciprocity, can be used to evaluate any Legendre symbol. For example:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left ( \frac{12345}{331}\right )&=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right ) \\ &= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right ) \\ &= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right ) \\ &= (-1)\left (\frac{331}{3}\right) \left(\frac{331}{5}\right) (-1) \left(\frac{331}{7}\right) (-1)\left (\frac{331}{23}\right ) \\ &= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{9}{23}\right )\\ &= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{3^2}{23}\right )\\ &= -(1) (1) (1) (1) \\ &= -1. \end{align}}

Or using a more efficient computation:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left ( \frac{12345}{331}\right )=\left ( \frac{98}{331}\right )=\left ( \frac{2 \cdot 7^2}{331}\right )=\left ( \frac{2}{331}\right )=(-1)^\tfrac{331^2-1}{8}=-1.}

The article Jacobi symbol has more examples of Legendre symbol manipulation.

Since no efficient factorization algorithm is known, but efficient modular exponentiation algorithms are, in general it is more efficient to use Legendre's original definition, e.g.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left(\frac{98}{331}\right) &\equiv 98^{\frac{331-1}{2}} &\pmod{331} \\ &\equiv 98^{165} &\pmod{331} \\ &\equiv 98 \cdot (98^2)^{82} &\pmod{331} \\ &\equiv 98 \cdot 5^{82} &\pmod{331} \\ &\equiv 98 \cdot 25^{41} &\pmod{331} \\ &\equiv 133 \cdot 25^{40} &\pmod{331} \\ &\equiv 133 \cdot 294^{20} &\pmod{331} \\ &\equiv 133 \cdot 45^{10} &\pmod{331} \\ &\equiv 133 \cdot 39^5 &\pmod{331} \\ &\equiv 222 \cdot 39^4 &\pmod{331} \\ &\equiv 222 \cdot 197^2 &\pmod{331} \\ &\equiv 222 \cdot 82 &\pmod{331} \\ &\equiv -1 &\pmod{331} \end{align}}

using repeated squaring modulo 331, reducing every value using the modulus after every operation to avoid computation with large integers.

Table of values

The following is a table of values of Legendre symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right)} with p ≤ 127, a ≤ 30, p odd prime.

a
p
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
3 −1 −1 0 −1 −1 0 1 −1 −0 1 −1 0 1 −1 0 −1 −1 0 1 −1 0 1 −1 0 −1 −1 0 1 −1 0
5 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0
7 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1
11 1 −1 1 1 1 −1 −1 −1 1 −1 0 1 −1 1 1 1 −1 −1 −1 1 −1 0 1 −1 1 1 1 −1 −1 −1
13 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 0 1 −1 1 1
17 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1
19 1 −1 −1 1 1 1 1 −1 1 −1 1 −1 −1 −1 −1 1 1 −1 0 1 −1 −1 1 1 1 1 −1 1 −1 1
23 1 1 1 1 −1 1 −1 1 1 −1 −1 1 1 −1 −1 1 −1 1 −1 −1 −1 −1 0 1 1 1 1 −1 1 −1
29 1 −1 −1 1 1 1 1 −1 1 −1 −1 −1 1 −1 −1 1 −1 −1 −1 1 −1 1 1 1 1 −1 −1 1 0 1
31 1 1 −1 1 1 −1 1 1 1 1 −1 −1 −1 1 −1 1 −1 1 1 1 −1 −1 −1 −1 1 −1 −1 1 −1 −1
37 1 −1 1 1 −1 −1 1 −1 1 1 1 1 −1 −1 −1 1 −1 −1 −1 −1 1 −1 −1 −1 1 1 1 1 −1 1
41 1 1 −1 1 1 −1 −1 1 1 1 −1 −1 −1 −1 −1 1 −1 1 −1 1 1 −1 1 −1 1 −1 −1 −1 −1 −1
43 1 −1 −1 1 −1 1 −1 −1 1 1 1 −1 1 1 1 1 1 −1 −1 −1 1 −1 1 1 1 −1 −1 −1 −1 −1
47 1 1 1 1 −1 1 1 1 1 −1 −1 1 −1 1 −1 1 1 1 −1 −1 1 −1 −1 1 1 −1 1 1 −1 −1
53 1 −1 −1 1 −1 1 1 −1 1 1 1 −1 1 −1 1 1 1 −1 −1 −1 −1 −1 −1 1 1 −1 −1 1 1 −1
59 1 −1 1 1 1 −1 1 −1 1 −1 −1 1 −1 −1 1 1 1 −1 1 1 1 1 −1 −1 1 1 1 1 1 −1
61 1 −1 1 1 1 −1 −1 −1 1 −1 −1 1 1 1 1 1 −1 −1 1 1 −1 1 −1 −1 1 −1 1 −1 −1 −1
67 1 −1 −1 1 −1 1 −1 −1 1 1 −1 −1 −1 1 1 1 1 −1 1 −1 1 1 1 1 1 1 −1 −1 1 −1
71 1 1 1 1 1 1 −1 1 1 1 −1 1 −1 −1 1 1 −1 1 1 1 −1 −1 −1 1 1 −1 1 −1 1 1
73 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 −1 1 −1 1 1 −1 −1 −1 1 1 1 −1 1 −1 −1 −1
79 1 1 −1 1 1 −1 −1 1 1 1 1 −1 1 −1 −1 1 −1 1 1 1 1 1 1 −1 1 1 −1 −1 −1 −1
83 1 −1 1 1 −1 −1 1 −1 1 1 1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 −1 1 1 1 1 1 1
89 1 1 −1 1 1 −1 −1 1 1 1 1 −1 −1 −1 −1 1 1 1 −1 1 1 1 −1 −1 1 −1 −1 −1 −1 −1
97 1 1 1 1 −1 1 −1 1 1 −1 1 1 −1 −1 −1 1 −1 1 −1 −1 −1 1 −1 1 1 −1 1 −1 −1 −1
101 1 −1 −1 1 1 1 −1 −1 1 −1 −1 −1 1 1 −1 1 1 −1 1 1 1 1 1 1 1 −1 −1 −1 −1 1
103 1 1 −1 1 −1 −1 1 1 1 −1 −1 −1 1 1 1 1 1 1 1 −1 −1 −1 1 −1 1 1 −1 1 1 1
107 1 −1 1 1 −1 −1 −1 −1 1 1 1 1 1 1 −1 1 −1 −1 1 −1 −1 −1 1 −1 1 −1 1 −1 1 1
109 1 −1 1 1 1 −1 1 −1 1 −1 −1 1 −1 −1 1 1 −1 −1 −1 1 1 1 −1 −1 1 1 1 1 1 −1
113 1 1 −1 1 −1 −1 1 1 1 −1 1 −1 1 1 1 1 −1 1 −1 −1 −1 1 −1 −1 1 1 −1 1 −1 1
127 1 1 −1 1 −1 −1 −1 1 1 −1 1 −1 1 −1 1 1 1 1 1 −1 1 1 −1 −1 1 1 −1 −1 −1 1

Notes

  1. ↑ Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris. p. 186 (published on year VI of the French Republican calendar, thus in 1797 or 1798).
  2. ↑ Hardy & Wright, Thm. 83.
  3. ↑ Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
  4. ↑ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463–495
  5. ↑ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in Untersuchungen ... pp. 501–505
  6. ↑ Lemmermeyer, ex. p. 31, 1.34
  7. ↑ Lemmermeyer, pp. 236 ff.

References

Retrieved from "https://wiki.tachyony.co.uk/w/index.php?title=Legendre_symbol&oldid=27328"