Legendre Symbol - Definition

Definition

Let p be an odd prime number. An integer a is a quadratic residue modulo p if it is congruent to a perfect square modulo p and is a quadratic nonresidue modulo p otherwise. The Legendre symbol is a function of a and p defined as follows:

\left(\frac{a}{p}\right) = \begin{cases} \;\;\,1 \text{ if } a \text{ is a quadratic residue modulo}\ p \text{ and } a \not\equiv 0\pmod{p} \\ -1 \text{ if } a \text{ is a quadratic non-residue modulo}\ p\\ \;\;\,0 \text{ if } a \equiv 0 \pmod{p}. \end{cases}

Legendre's original definition was by means of an explicit formula:

By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent. Thus Legendre's contribution lay in introducing a convenient notation that recorded quadratic residuosity of a mod p. For the sake of comparison, Gauss used the notation, according to whether a is a residue or a non-residue modulo p.

For typographical convenience, the Legendre symbol is sometimes written as (a|p) or (a/p). The sequence (a|p) for a equal to 0,1,2,... is periodic with period p and is sometimes called the Legendre sequence, with {0,1,−1} values occasionally replaced by {1,0,1} or {0,1,0}.

Read more about this topic:  Legendre Symbol

Famous quotes containing the word definition:

    “... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
    —George Eliot [Mary Ann (or Marian)

    “Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.”
    —Willard Van Orman Quine (b. 1908)

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)