Legendre symbol
| If n is an integer and p is an
odd prime, then |
( |
n
p |
) |
is |
{ |
0 if n≡0 (mod p),
1 if n is a square (mod p), and
-1 otherwise |
| if n=1, or any square smaller
than p, then |
( |
n
p |
) |
= 1, |
Properties of the Legendre symbol
| |
( |
a
p |
) |
= |
( |
b
p |
) |
|
whenever a≡b (mod p)
|
| |
( |
1
p |
) |
= 1. In fact, |
( |
n
p |
) |
= 1 |
whenever n is a non-zero square
|
| |
( |
−1
p |
) |
= (-1)(p-1)/2, or |
{ |
1 if p≡1 (mod 4),
-1 if p≡-1 (mod 4), |
These first four properties come directly from Euler's Criterion.
| |
( |
−1
p |
) |
= (-1)(p-1)/2, or |
{ |
1 if p≡1 (mod 4),
-1 if p≡-1 (mod 4), |
Internet references
Related
pages in this website
Euler's Criterion — a
way to tell if a number is a quadratic residue (mod p)
| Jacobi symbol — |
( |
a
n |
) |
, where a is any integer, and n
is a positive integer greater than 2, an extension of the Legendre
symbol. |
| Kronecker symbol — |
( |
a
n |
) |
, where a and n are any integers,
an extension of the Jacobi symbol. |
|
