Ok, here’s the third installation. Getting a little tired of repeatedly saying “*a* is/isn’t a square mod *p*“, we introduce a new notation.

Definition. Let p be an odd prime and a be an integer coprime to p. TheLegendre symbolis given by:

For completeness, one also defines if *a* is a multiple of *p*, but we won’t need this for now. From our previous post, we know the following:

- ;
- hence from property 1, ;
- for special values of
*a*, we have and .

From the multiplicative property (2), it thus suffices to consider for odd prime *q* ≠ *p*. This is where we’ll pull the next rabbit out of the hat (i.e. quote a result without proof).

Quadratic Reciprocity Theorem. If p, q are distinct odd primes, then.

In other words, and are identical *unless* both *p* and *q* are congruent to 3 mod 4.

–

**Example 1**. Determine whether 31 is a square modulo 73.

**Solution**. We will repeatedly use the quadratic reciprocity rule:

- since 73 is 1 mod 4, so ;
- since 31 ≡ 11 ≡ 3 (mod 4), so since 9 is clearly a square mod 11.

Thus, 31 is not a square modulo 73. ♦

**Example 2**. Classify all odd primes *p* ≠ 3 such that 3 is a square modulo *p*.

**Solution**. Use the quadratic reciprocity: . Since the RHS depends on *p* modulo 4, we need to consider *p* modulo 12. Thus, 3 is a square modulo *p* iff .

- If , then and , i.e. .
- If , then and , i.e. .

Thus 3 is a square mod *p* iff *p* ≡ ±1 (mod 12). ♦

**Example 3**. Classify all odd primes *p* ≠ 3 such that -3 is a square modulo *p*.

**Solution**. From example 1, we have . Thus,

.

And -3 is a square mod *p* iff *p* ≡ 1 (mod 3). ♦

Coming up next: applying quadratic residues in conjunction with order of an element modulo *n* to solve IMO-type problems. The gist of the idea is this: suppose *p* is a prime and *a* be not divisible by *p*; let the (multiplicative) order of *a* modulo *p* be denoted *d*. We already know that *d* | (*p*-1). It turns out that *a* is a square modulo *p* if and only if is even.

To see why, just let *g* be a primitive root modulo *p*. And write . Now *d* is the smallest positive integer for which . Thus *d* is the smallest positive integer such that *rd* is a multiple of (*p*-1). A moment of thought will tell you that thus *d* = (*p*-1)/gcd(*r*, *p*-1) (prove it! just write *g* = gcd(*r*, *p*-1) and *r* = *gu*, (*p*-1) = *gv* where (*u*, *v*) = 1 … ).

*Thus, our desired result follows from the fact that a is a square modulo p if and only if r is even. *If you’re not sure why the fact is true, refer to part II of the notes. If you’re still confused, fret not, we will include some concrete examples in the next installation.