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)

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

    “Every natural fact is a symbol of some spiritual fact. Every appearance in nature corresponds to some state of the mind, and that state of the mind can only be described by presenting that natural appearance as its picture.”
    —Ralph Waldo Emerson (1803–1882)