# Legendre Symbol Calculator

## Evaluation rules (& names)

Suppose $$p$$ is an odd prime. Then:
EvalZero: $$\left(\frac{0}{p}\right) = 0$$
EvalOne: $$1^2 \equiv 1 \pmod{p}$$, so $$\left(\frac{1}{p}\right) = 1$$
Modulo: If $$a \equiv b \pmod{p}$$, then $$\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$$
Multiplicative: For all $$a, b$$, we have $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$ See Lemma 15.13 in the notes.
Power: (This is really just a consequence of Multiplicative). For all $$a$$, we have $$\left(\frac{a^k}{p}\right) = \left(\frac{a}{p}\right)^k$$ In particular, $$\left(\frac{a^k}{p}\right) = \begin{cases} 1 & \mathrm{if} \; k \; \mathrm{is} \; \mathrm{even} \\ \left(\frac{a}{p}\right) & \mathrm{if} \; k \; \mathrm{is} \; \mathrm{odd} \end{cases}$$ See Lemma 15.13 in the notes.
EvalMinusOne: $$\left(\frac{p-1}{p}\right) = \begin{cases} 1 & \mathrm{if} \; p \equiv 1 \pmod{4} \\ -1 & \mathrm{if} \; p \equiv -1 \pmod{4} \\ \end{cases}$$ See Theorem 15.11 in the notes.
EvalTwo: $$\left(\frac{2}{p}\right) = \begin{cases} 1 & \mathrm{if} \; p \equiv \pm 1 \pmod{8} \\ -1 & \mathrm{if} \; p \equiv \pm 3 \pmod{8} \\ \end{cases}$$ See Proposition 16.9 in the notes.
Reciprocity: Let $$q$$ be an odd prime distinct from $$p$$. If $$p \equiv q \equiv -1 \pmod{4}$$, then $$\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$$ Otherwise, $$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$$ See Theorem 16.1 in the notes.

## What is this?

This was a fun little app I put together while revising for a number theory exam. The core idea is that the app helps you teach yourself to determine whether a given number $$y$$ is a quadratic residue modulo some odd prime $$p$$, that is, if there exists $$x$$ such that $$x^2 \equiv y \pmod{p}$$.

The Legendre symbol $$\left(\frac{y}{p}\right)$$ is defined to be $$0$$ if $$y$$ is a multiple of $$p$$, $$1$$ if $$y$$ is a quadratic residue modulo $$p$$, and $$-1$$ otherwise.

The notes referred to within the evaluation rules are the set of lecture notes which were used in the 2017/18 Introduction to Number Theory course at the University of Edinburgh. If you don't have those notes, a little googling will hopefully help you find proofs of these facts. Alternatively, you might try to prove them yourself!