|
|
|
| If n is an integer and p is an odd prime, then | ( | n p |
) | is | { |
0 if n≡0 (mod p), |
| From Euler's Criterion, we can see that | ( | n p |
) | = n(p-1)/2. |
if n=1, or any square smaller than p, then ( n
p) = 1,
| ( | ab p |
) | = | ( | a p |
)( | b p |
) |
for all integers a,b, because the Legendre symbol is "completely multiplicative". |
| ( | a p |
) | = | ( | b p |
) |
whenever a≡b (mod p) |
| ( | 1 p |
) | = 1. In fact, | ( | n p |
) | = 1 |
whenever n is a non-zero square (mod p) |
| ( | −1 p |
) | = (-1)(p-1)/2, or | { |
1 if p≡1 (mod 4), |
These first four properties come directly from Euler's Criterion. In general,
| ( | a p |
) | = a(p-1)/2 (mod p) |
| ( | p q |
) | = | ( | q p |
) | (-1)[(p-1)/2][(q-1)/2], |
whenever p and q are both prime. This can be simplified to |
| ( | p q |
) | = | ( | q p |
) | (-1)(p-1)(q-1)/4, |
whenever p and q are both prime. |
Another way to express this is
| ( | p q |
) | = | ( | q p |
) | , |
for primes p,q, and either p=4k+1 for some k, or q=4k+1 for some k. |
| ( | p q |
) | = | (-1) | ( | q p |
) | , |
for primes p,q, and p=4k+3 for some k, and q=4k+3 for some k. |
| ( | 2 p |
) | = 2(p-1)/2 (mod p), or | ( | 2 p |
) | = (-1)(p^2-1)/2 (mod p), or | { |
1 if p≡±1 (mod 8), |
which is proved using Gauss' Lemma.
| ( | 3 p |
) | = 3(p-1)/2 (mod p), or | { |
1 if p≡±1 (mod 12), |
which is proved using Quadratic Reciprocity.
( 3
p) = ( p
3) if p≡1 (mod 4), and ( 3
p) = (-1) ( p
3) if p≡-1 (mod 4). Since 1 is the only quadratic residue (mod 3), and -1 is the only quadratic non-residue (mod 3), the result follows. The next two examples are done the same way. Note that the case of 5, 13, etc. are easier because, for example,
( 5
p) = ( p
5) for all values of p, since 5≡1 (mod 4).
| ( | 5 p |
) | = 5(p-1)/2 (mod p), or | { |
1 if p≡±1 (mod 5), |
| ( | 6 p |
) | = 6(p-1)/2 (mod p), or | { |
1 if p≡±1,5 (mod 24), |
| ( | 7 p |
) | = 7(p-1)/2 (mod p), or | { |
1 if p≡±1,3,9 (mod 28), |
| ( | -2 p |
) | = -2(p-1)/2 (mod p), or | { |
1 if p≡1,3 (mod 8), |
| ( | -3 p |
) | = -3(p-1)/2 (mod p), or | { |
1 if p≡1 (mod 6), |
| ( | -5 p |
) | = -5(p-1)/2 (mod p), or | { |
1 if p≡1,3,7,9 (mod 20), |
| ( | -6 p |
) | = -6(p-1)/2 (mod p), or | { |
1 if p≡1,5,7,11 (mod 24), |
| ( | -7 p |
) | = -7(p-1)/2 (mod p), or | { |
1 if p≡1,9,11,15,23,25 (mod 28), |
Mathworld: Legendre Symbol, Quadratic Residue
Euler's Criterion — a way to tell if a number is a quadratic residue, i.e. a square, (mod p): If p is an odd prime, and a is an integer coprime to p, then a is a quadratic residue (mod p) iff a(p-1)/2 ≡ 1 (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. Quadratic Residues - Modular Arithmetic and the Quadratic Equations ax^2+bx+c=0, a(p-1)/2 ≡�1 (mod P), a is a quadratic residue (mod p) iff a^((p-1)/2)≡1 (mod p), Legendre Symbol, Prime of form 4k+1 is a "Pythagorean Prime" because it can be expressed as the sum of two squares, Legendre (2/p) = (p^2-1)/8 (mod p) attributed to Gauss, quadratic reciprocity law, computing sqrt (mod p) using Tonelli-Shanks algorithm
The webmaster and author of this Math Help site is Graeme McRae.