6.1.25 Legendre symbol
If n is prime, the Legendre symbol of a is written
(a/n) and defined by:
| ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | = | ⎧
⎪
⎨
⎪
⎩ | 0 | if a≡ 0(mod n ) |
1 | if a ≢0 (mod n ) and a≡ b2 (mod n ) |
−1 | if a ≢0 (mod n ) and a ≢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:
| | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | . | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ |
| | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
|
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