Legendre symbol

The Legendre symbol is a function used in number theory . Introduced by the French mathematician A. M. Legendre . The Legendre symbol is a special case of the Jacobi symbol , which, in turn, is a special case of the Kronecker-Jacobi symbol , which is sometimes called the Legendre-Jacobi-Kronecker symbol.

Definition

Let a be an integer and p be a prime other than 2. Legendre symbol $\textstyle \left({\frac {a}{p}}\right)$ ${\ displaystyle \ textstyle \ left ({\ frac {a} {p}} \ right)}$ defined as follows:

$\textstyle \left({\frac {a}{p}}\right)=0$ ${\ displaystyle \ textstyle \ left ({\ frac {a} {p}} \ right) = 0}$ if a is divisible by p ;
$\textstyle \left({\frac {a}{p}}\right)=1$ ${\ displaystyle \ textstyle \ left ({\ frac {a} {p}} \ right) = 1}$ if a is a quadratic residue modulo p (i.e., there exists an integer x such that $x^{2}\equiv a{\pmod {p}}$ {\ displaystyle x ^ {2} \ equiv a {\ pmod {p}}} ) and a is not divisible by p ;
$\textstyle \left({\frac {a}{p}}\right)=-1$ ${\ displaystyle \ textstyle \ left ({\ frac {a} {p}} \ right) = - 1}$ if a is a quadratic non-residue modulo p .

Properties

Multiplicativeness : $($ $a$ $b$ $p$ $)$ $=$ $($ $a$ $p$ $)$ $($ $b$ $p$ $)$ {\ displaystyle \ left ({\ frac {ab} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) \ left ({\ frac {b} {p}} \ right)} . In particular,
- If $a$ ${\ displaystyle a}$ not divided by $p$ ${\ displaystyle p}$ then $\left({\frac {a^{2}}{p}}\right)=1.$ ${\ displaystyle \ left ({\ frac {a ^ {2}} {p}} \ right) = 1.}$
- If a $a=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}$ ${\ displaystyle a = p_ {1} ^ {\ alpha _ {1}} \ cdot p_ {2} ^ {\ alpha _ {2}} \ cdot \ ldots \ cdot p_ {k} ^ {\ alpha _ {k }}}$ - canonical decomposition $a$ ${\ displaystyle a}$ to simple factors then
  $\left({\frac {a}{p}}\right)=\left({\frac {p_{1}}{p}}\right)^{\alpha _{1}{\pmod {2}}}\cdot \left({\frac {p_{2}}{p}}\right)^{\alpha _{2}{\pmod {2}}}\cdots \left({\frac {p_{k}}{p}}\right)^{\alpha _{k}{\pmod {2}}}.$ ${\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {p_ {1}} {p}} \ right) ^ {\ alpha _ {1} {\ pmod {2}}} \ cdot \ left ({\ frac {p_ {2}} {p}} \ right) ^ {\ alpha _ {2} {\ pmod {2}}} \ cdots \ left ({\ frac {p_ {k}} {p}} \ right) ^ {\ alpha _ {k} {\ pmod {2}}}.}$
If a $a\equiv b{\pmod {p}}$ ${\ displaystyle a \ equiv b {\ pmod {p}}}$ then
$\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).$ ${\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right).}$
$\left({\frac {1}{p}}\right)=1.$ ${\ displaystyle \ left ({\ frac {1} {p}} \ right) = 1.}$
$\left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2}.$ ${\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {(p-1) / 2}.}$
$\left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}.$ ${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {(p ^ {2} -1) / 8}.}$
Quadratic reciprocity law : Let p and q be unequal odd primes, then
$\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}\cdot \left({\frac {p}{q}}\right).$ ${\ displaystyle \ left ({\ frac {q} {p}} \ right) = (- 1) ^ {{\ frac {p-1} {2}} \ cdot {\ frac {q-1} {2 }}} \ cdot \ left ({\ frac {p} {q}} \ right).}$

If a

p\equiv q{\pmod {4\cdot a}}

{\ displaystyle p \ equiv q {\ pmod {4 \ cdot a}}}

then

\left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)

{\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {a} {q}} \ right)}

.

Among the numbers $1\leqslant a\leqslant p-1$ ${\ displaystyle 1 \ leqslant a \ leqslant p-1}$ exactly half has a Legendre symbol equal to +1, and the other half has −1.
Gauss quadratic residue lemma
Euler formula

\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}.

{\ displaystyle \ left ({\ frac {a} {p}} \ right) \ equiv a ^ {(p-1) / 2} {\ pmod {p}}.}

Literature

Vinogradov I. M. Fundamentals of number theory . - Moscow: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .

Legendre symbol

Definition

Properties

Literature

More articles: