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!

By Harry Garrood / Source on GitHub