## 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.)

Note that the third case should never apply in the context of this module, since the Legendre symbol on the module is guaranteed to satisfy 0 < q < p. The third case is only enumerated here for the sake of mathematical completeness.