LegendreSymbol

The Legendre symbol.

Syntax

• LegendreSymbol(a, p)

  • a is an integer

  • p is an odd prime

Description

                       ⎧ +1   if a is a quadratic residue mod p and a ≢ 0 (mod p)
LegendreSymbol(a, p) = ⎨ −1   if a is a non-quadratic residue mod p
                       ⎩  0   if a ≡ 0 (mod p).

Examples

matrix(compute(LegendreSymbol(a, prime(n)), n, 2, 20, a, 1, 20))

⎛ 1  −1   0   1  −1   0   1  −1   0   1  −1   0   1  −1   0   1  −1   0   1  −1⎞
⎜ 1  −1  −1   1   0   1  −1  −1   1   0   1  −1  −1   1   0   1  −1  −1   1   0⎟
⎜ 1   1  −1   1  −1  −1   0   1   1  −1   1  −1  −1   0   1   1  −1   1  −1  −1⎟
⎜ 1  −1   1   1   1  −1  −1  −1   1  −1   0   1  −1   1   1   1  −1  −1  −1   1⎟
⎜ 1  −1   1   1  −1  −1  −1  −1   1   1  −1   1   0   1  −1   1   1  −1  −1  −1⎟
⎜ 1   1  −1   1  −1  −1  −1   1   1  −1  −1  −1   1  −1   1   1   0   1   1  −1⎟
⎜ 1  −1  −1   1   1   1   1  −1   1  −1   1  −1  −1  −1  −1   1   1  −1   0   1⎟
⎜ 1   1   1   1  −1   1  −1   1   1  −1  −1   1   1  −1  −1   1  −1   1  −1  −1⎟
⎜ 1  −1  −1   1   1   1   1  −1   1  −1  −1  −1   1  −1  −1   1  −1  −1  −1   1⎟
⎜ 1   1  −1   1   1  −1   1   1   1   1  −1  −1  −1   1  −1   1  −1   1   1   1⎟
⎜ 1  −1   1   1  −1  −1   1  −1   1   1   1   1  −1  −1  −1   1  −1  −1  −1  −1⎟
⎜ 1   1  −1   1   1  −1  −1   1   1   1  −1  −1  −1  −1  −1   1  −1   1  −1   1⎟
⎜ 1  −1  −1   1  −1   1  −1  −1   1   1   1  −1   1   1   1   1   1  −1  −1  −1⎟
⎜ 1   1   1   1  −1   1   1   1   1  −1  −1   1  −1   1  −1   1   1   1  −1  −1⎟
⎜ 1  −1  −1   1  −1   1   1  −1   1   1   1  −1   1  −1   1   1   1  −1  −1  −1⎟
⎜ 1  −1   1   1   1  −1   1  −1   1  −1  −1   1  −1  −1   1   1   1  −1   1   1⎟
⎜ 1  −1   1   1   1  −1  −1  −1   1  −1  −1   1   1   1   1   1  −1  −1   1   1⎟
⎜ 1  −1  −1   1  −1   1  −1  −1   1   1  −1  −1  −1   1   1   1   1  −1   1  −1⎟
⎝ 1   1   1   1   1   1  −1   1   1   1  −1   1  −1  −1   1   1  −1   1   1   1⎠

∑(ans)

34

See also

• JacobiSymbol

• KroneckerSymbol