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)

    “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)

    “Your true traveller finds boredom rather agreeable than painful. It is the symbol of his liberty—his excessive freedom. He accepts his boredom, when it comes, not merely philosophically, but almost with pleasure.”
    —Aldous Huxley (1894–1963)