## On the Subject of the Legendre Symbol

For those of you who were afraid of fractions in grade school, be thankful you didn’t have to deal with these.

- Each display shows a whole number between 1 and 999.
- The number on the top display is guaranteed to be less than the number on the bottom display.
- The number on the bottom display is guaranteed to be a three-digit prime number.
- To disarm this module, let q and m be the numbers on the top and bottom displays respectively. If q is a quadratic residue modulo m, press the button labeled “R.” Otherwise, press the button labeled “N.”
- Pressing the wrong button will administer a strike and cause the numbers on the displays to change.

### Useful Notes on Quadratic Residues

An integer q is said to be a *quadratic residue* modulo m if it is congruent to some perfect square modulo m, that is, if there exists some integer x such that x^{2} ≡ q (mod m). If no such value exists, then q is said to be a *quadratic nonresidue* modulo m.

For example, since perfect squares leave remainders of 0, 1, 4, 5, 6, and 9 when divided by 10, any number that also leaves one of these remainders when divided by 10 (including said remainders themselves) is a quadratic residue modulo 10. Any other number is a quadratic nonresidue.

In the special case where the modulus is an odd prime p, quadratic residuosity can be described using the *Legendre symbol*, defined as follows:

(qp) = {

(The notion of a “multiple” in the above definition includes negative numbers and zero. For example, 14, 49, 0, and -21 are all considered to be multiples of 7.)

An interesting fact about the number of quadratic residues modulo an odd prime is as follows, the proof of which is left as an exercise to the reader:

** Proposition 1.** If p is an odd prime, then

*exactly half*of the integers between 1 and p-1 inclusive are quadratic residues modulo p; the rest are nonresidues.