Legendre Symbol - Properties of The Legendre Symbol

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.

  • The Legendre symbol is periodic in its first (or top) argument: if a ≡ b (mod p), then
\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).
  • The Legendre symbol is a completely multiplicative function of its top argument:
\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:
\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 is the unique quadratic (or order 2) Dirichlet character modulo p.
  • The first supplement to the law of quadratic reciprocity:
\left(\frac{-1}{p}\right) = (-1)^\tfrac{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:
\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 for small values of a:
  • For an odd prime p ≠ 3,
\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,
\left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{p+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
F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p,\;\;\; F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.

For example,

\begin{align} &(\tfrac{2}{5}) &= &-1, &F_3 &= 2, \;\;\;\;&F_2 &=1,\\ &(\tfrac{3}{5}) &= &-1, &F_4 &= 3,&F_3&=2,\\ &(\tfrac{5}{5}) &= &\;\;\;\;0, &F_5 &= 5,\\ &(\tfrac{7}{5}) &= &-1, &F_8 &= 21,&F_7&=13,\\ &(\tfrac{11}{5}) &= &\;\;\,1, &F_{10} &= 55, &F_{11}&=89. \end{align}
This result comes from the theory of Lucas sequences, which are used in primality testing. See Wall–Sun–Sun prime.

Read more about this topic:  Legendre Symbol

Famous quotes containing the words properties of the, properties of, properties and/or symbol:

    “A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
    —Ralph Waldo Emerson (1803–1882)

    “A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
    —Ralph Waldo Emerson (1803–1882)

    “The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
    —John Locke (1632–1704)

    “A pool is, for many of us in the West, a symbol not of affluence but of order, of control over the uncontrollable. A pool is water, made available and useful, and is, as such, infinitely soothing to the western eye.”
    —Joan Didion (b. 1934)