Lagmental Vicfred

Euler's Criterion Computes the Legendre Symbol by Exponentiation by Vicfred

Raising a nonzero residue to half of p minus one distinguishes squares from nonsquares. This is a compact note, but the quantifiers and hypotheses stay on the page.

Start locally

For an odd prime \(p\), the Legendre symbol \(\left(\frac ap\right)\) records whether \(a\) is a nonzero square modulo \(p\). Reciprocity exchanges numerator and denominator up to a sign.

$$ p\nmid a $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p $$

Compute before generalising

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ p=11,\ a=2:\qquad2^5=32\equiv-1\pmod{11}\quad\Longrightarrow\quad\left(\frac2{11}\right)=-1 $$

The global view

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad p\nmid a,\\[5pt] \mathsf{C}\;&:\quad a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p. \end{aligned} $$

Edge conditions

The symbol is defined modulo an odd prime and is not ordinary division. Composite odd denominators require the Jacobi symbol, which can equal one without certifying a square.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Fri 06 November 2009. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.