6.5.24  Legendre symbol: legendre_symbol

If n is prime, the Legendre symbol of a is written (a/n) and defined by:

The Legendre symbol satisfies the following properties.

• If n is prime:

  a

  n−1 2

  =

  ⎛ ⎜ ⎜ ⎝

  a n

  ⎞ ⎟ ⎟ ⎠

  modn

• ⎛ ⎜ ⎜ ⎝ p q ⎞ ⎟ ⎟ ⎠ . ⎛ ⎜ ⎜ ⎝ q p ⎞ ⎟ ⎟ ⎠ = (−1) p−1 2   .(−1) q−1 2   if p and q are odd and positive  ⎛ ⎜ ⎜ ⎝ 2 p ⎞ ⎟ ⎟ ⎠ = (−1) p2−1 8     ⎛ ⎜ ⎜ ⎝ −1 p ⎞ ⎟ ⎟ ⎠ = (−1) p−1 2

The legendre_symbol command computes the Legendre symbol.

• legendre_symbol takes two arguments:
  a and n, integers.
• legendre_symbol(a,n) returns the Legendre symbol (a/n).

Examples.

• Input:
  legendre_symbol(26,17)
  Output:

  1

• Input:
  legendre_symbol(27,17)
  Output:

  −1

• Input:
  legendre_symbol(34,17)
  Output:

  0