On the Subject of the Legendre Symbol

Number Theory is pain, imagine proving all these💀

Properties of the Legendre Symbol

Use any rules that apply till you get a single number: 1 or -1.

Press “R” if your final result is +1. “N” if -1.

p is an odd prime; p and q are distinct odd primes.

1. Periodicity. If a ≡ b (mod p), then:

   (ap) = (bp)

2. Total Multiplicativity. For all integers a, b (,c and so on):

   (abp) = (ap)(bp) & (abcp) = (ap) (bp) (cp)

   and so on. Useful if numerator is a composite number.

3. *Corollary of 2. For any integer a,

   (a²p) = (1p) = 1

4. Quadratic Reciprocity (QR).

   If p ≡ 1 (mod 4) or q ≡ 1 (mod 4), then (pq) = (qp). Otherwise, (pq) = -(qp).

5. 1st Supplement to QR.

   (-1p) = { +1-1 if p ≡ 1 (mod 4)if p ≡ 3 (mod 4)

6. 2nd Supplement to QR.

   (2p) = { +1-1 if p ≡ 1 or 7 (mod 8)if p ≡ 3 or 5 (mod 8)

More Supplements to QR

Below states conditions for when (?/p) is 1 or -1.

(?/p)	= 1	= -1
(-1/p)	p ≡ 1 (mod 4)	p ≡ 3 (mod 4)
(2/p)	p ≡ 1, 7 (mod 8)	p ≡ 3, 5 (mod 8)
(3/p)	p ≡ 1, 11 (mod 12)	p ≡ 5, 7 (mod 12)
(5/p)	p ≡ 1, 4 (mod 5)	p ≡ 2, 3 (mod 5)
(6/p)	p ≡ 1, 5, 19, 23 (mod 24)	p ≡ 7, 11, 13, 17 (mod 24)
(7/p)	p ≡ 1, 3, 9, 19, 25, 27 (mod 28)	p ≡ 5, 11, 13, 15, 17, 23 (mod 28)

For example, since 373 mod 24 = 13 and 69 mod 5 = 4, thus

(6373) = -1 (in -1 column)

(569) = 1 (in 1 column)

Listing Out Quadratic Residues

The table below lists the value of (q/p) for small values.

p	q where (q/p) = 1
3	1
5	1, 4
7	1, 2, 4
11	1, 3, 4, 5, 9
13	1, 3, 4, 9, 10, 12

For example, from the table,

(913) = 1 (since it’s on the list)

(611) = -1 ; (since it’s NOT on the list)

Computing a Legendre Symbol’s Value

By iteratively applying the properties on the previous page, it is possible to express the value of a Legendre symbol in terms of other Legendre symbols with smaller moduli.

Eventually, these moduli will become small enough that the Legendre symbols’ values can be computed either by listing out the first few perfect squares and checking their remainders by hand (see the section below) or by recognizing a perfect square in a Legendre symbol’s “top” argument, which automatically gives said Legendre symbol a value of +1 by definition.

For example, here’s one way to show that 14 is NOT a quadratic residue modulo 41. New terms generated using one of the five rules above are marked accordingly:

(1441) = (241)(741)(rule 2) = (-1)^412-18(rule 6)·(417)(rule 4) = (-1)²¹⁰·(-17)(rule 1) = 1·(-1)^7-12(rule 5) = (-1)³ = -1

Since the Legendre symbol evaluates to -1, it follows by definition that 14 is not a quadratic residue modulo 41.

There are multiple ways in which one may apply these rules to arrive at a final answer, some of which are faster and more efficient than others, but they will all lead to the same answer. Experiment with different algorithms to find one that best suits your needs.