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)

    “The glance is natural magic. The mysterious communication established across a house between two entire strangers, moves all the springs of wonder. The communication by the glance is in the greatest part not subject to the control of the will. It is the bodily symbol of identity with nature. We look into the eyes to know if this other form is another self, and the eyes will not lie, but make a faithful confession what inhabitant is there.”
    —Ralph Waldo Emerson (1803–1882)