7.1.25 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, then a^n−1/2≡ (a/n) (mod n ) .
• The following holds for odd and positive numbers p and k:

  ⎛ ⎜ ⎜ ⎝

  p q

  ⎞ ⎟ ⎟ ⎠

  .

  ⎛ ⎜ ⎜ ⎝

  q p

  ⎞ ⎟ ⎟ ⎠

  =(−1)

  p−1 2

  .(−1)

  q−1 2

  ,

  ⎛ ⎜ ⎜ ⎝

  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