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 ab (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)

    Whether he admits it or not, a man has been brought up to look at money as a sign of his virility, a symbol of his power, a bigger phallic symbol than a Porsche.
    Victoria Billings (b. 1945)