Legendre symbolとは 意味・読み方・使い方

名詞

Legendre symbol (複数形 Legendre symbols)

1. (number theory) A mathematical function of an integer and a prime number, written ${\displaystyle \left({a \over p}\right)}$, which indicates whether a is a quadratic residue modulo p.
   • 1994, James K. Strayer, Elementary Number Theory, Waveland Press, 2002, Reissue, page 109,

     Our only method at present for the computation of Legendre symbols requires a possible consideration of ${\displaystyle \textstyle {\frac {p-1}{2}}}$ congruences (unless, of course, we are fortunate enough to encounter the desired quadratic residue along the way).

   • 2006, Neville Robbins, Beginning Number Theory, Jones & Bartlett, 2nd Edition, page 195,

     The Jacobi symbol, which generalizes the Legendre symbol, sheds some additional light on how to determine whether (7.29) has solutions when m has two or more distinct prime factors.

   • 2013, Song Y. Yan, Number Theory for Computing, Springer, page 149,

     Jacobi symbols can be used to facilitate the calculation of Legendre symbols. In fact, Legendre symbols can be eventually calculated by Jacobi symbols [17]. That is, the Legendre symbol can be calculated as if it were a Jacobi symbol. For example, consider the Legendre symbol ${\displaystyle \left({\frac {335}{2999}}\right)}$ where 335 = 5·67 is not a prime (of course, 2999 is a prime, otherwise, it is not a Legendre symbol).

使用する際の注意点

The symbol takes the values:

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

It is generalised to composite numbers by the Jacobi symbol, which is identical in form and range of values and is defined as a product of Legendre symbols.

参考

• Euler's criterion
• Jacobi symbol
• quadratic reciprocity