Legendre Symbol Calculator
Calculate the Legendre symbol (a/p) for an integer a and odd prime p.
Enter Values
Definition
The Legendre symbol (a/p) is defined as:
(a/p) = 0 if p divides a
(a/p) = 1 if a is a QR mod p
(a/p) = -1 if a is a NR mod p
Euler's Criterion
(a/p) ≡ a^((p-1)/2) (mod p)
Properties
- (ab/p) = (a/p)(b/p)
- (a^2/p) = 1
- (-1/p) = (-1)^((p-1)/2)
- (2/p) = (-1)^((p^2-1)/8)
Legendre Symbol
(7/13) = -1
a mod p
7
a^((p-1)/2) mod p
12
Interpretation
7 is a non-residue mod 13
Legendre Symbols for 1 to 12
123456789101112
QR: 6NR: 6
Calculation Method
Euler's Criterion
7^6 mod 13 = 12 ≡ -1