### 7.1.25 Legendre symbol

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

⎛
⎜
⎜
⎝

a
n

⎞
⎟
⎟
⎠

=

⎧
⎪
⎨
⎪
⎩

0 | ifa≡ 0(mod n)
1 | ifa≢0 (mod n)  anda≡b2(mod n)
−1 | ifa≢0 (mod n)  anda≢b2(mod n)

The Legendre symbol satisfies the following properties.

- If n is prime, then an−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

legendre_symbol(26,17)

1 |  |  |  |  |  |  |  |  |  |

legendre_symbol(27,17)

−1 |  |  |  |  |  |  |  |  |  |

legendre_symbol(34,17)

0 |  |  |  |  |  |  |  |  |  |