Legendre Symbol
The Legendre symbol is a function that encodes the information about whether a number is a quadratic residue modulo an odd prime. It is used in the law of quadratic reciprocity to simplify notation. Because the Legendre symbol is so compact and has such useful properties, it is an invaluable tool for doing computations and answering questions related to quadratic residues.
Definition
Let \(p\) be an odd prime and let \(a\) be an integer.
The Legendre symbol of \(a\) with respect to \(p\) is defined by
\[\left(\dfrac{a}{p}\right)=\begin{cases}1 & \text{ if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0\pmod{p}\\-1 & \text{ if } a \text{ is a quadratic non-residue modulo } p\\0 & \text{ if } a \equiv 0 \pmod{p}.\end{cases}\]
Properties
- (Euler's criterion) If \(p\) is an odd prime and \(a\) is an integer not divisible by \(p\), then \[a^{\frac{p-1}{2}}=\left(\dfrac{a}{p}\right)\pmod p.\]
- If \(a\equiv b \pmod p\), then \(\left(\dfrac{a}{p}\right)=\left(\dfrac{b}{p}\right)\).
- \(\left(\dfrac{ab}{p}\right)=\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)\); that is, the function \( f(a) = \left(\dfrac{a}{p} \right) \) is a completely multiplicative function.
- \(\left(\dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\), so it is \( 1 \) if and only if \( p \equiv 1 \) mod \( 4 \).
- \(\left(\dfrac{2}{p}\right)= (-1)^{\frac{p^2-1}{8}}\) for an odd prime \(p\), so it is \( 1 \) if and only if \( p \equiv \pm 1 \) mod \( 8 \).
- (The law of quadratic reciprocity) If \(p\) and \(q\) are distinct odd primes, we have \[\left(\dfrac{q}{p}\right)\left(\dfrac{p}{q}\right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}.\]
Proofs
Property 1: There are two parts: first compute \( a^{\frac{p-1}2} \) mod \( p \) for \( a \) a square, and then for \( a \) not a square.
If \( a = x^2 \), then \( x^{p-1} \equiv 1 \) mod \( p \) (Fermat's little theorem) can be rewritten as \( \big(x^2\big)^{(p-1)/2} \equiv 1 \) mod \( p \), so \( a^{\frac{p-1}2} \equiv 1 \) mod \( p \).
Now suppose \( a \) is not a square. Then note that if \( 1 \le x \le p-1 \), there is a unique \( y \) in the same range such that \( xy \equiv a \) mod \( p \). \((\)Writing \( y \equiv ax^{-1} \) mod \( p \) makes sense because every such \(x \) has a unique multiplicative inverse mod \( p.) \) Note that \( x \ne y \) because \( a \) is not a square. So the product of all the elements between \( 1 \) and \( p-1 \) can be broken up into \( \frac{p-1}2 \) pairs of products of the form \( xy \). This gives \(\big(\)with \( p' = \frac{p-1}{2}\big) \)
\[(p-1)! \equiv (x_1y_1)(x_2y_2)\cdots(x_{p'}y_{p'}) \equiv a \cdot a \cdots a \equiv a^{\frac{p-1}2} \pmod p\]
but \( (p-1)! \equiv -1 \) by Wilson's theorem, so the result follows. \(_\square \)
Property 2 is immediate from the definition.
Property 3 follows from Property 1 and the laws of exponents.
Property 4 follows from Property 1, because if two numbers are congruent mod an odd prime \( p \) and are both in \( \{-1,0,1\} \), they must be equal.
Properties 5 and 6 are discussed in the quadratic reciprocity page. Notice that Property 6 can be written alternatively as \[\left(\dfrac{q}{p}\right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}\left(\dfrac{p}{q}\right).\]
Properties 4 and 5 are often known as the first and second supplement to the law of quadratic reciprocity.
For all prime numbers \(p,\) where \(p > 5\), define \(C_p\) to be the set of all positive integers \(k\) such that \(k \le p-2\) with \(k\) and \(k+1\) as quadratic residues modulo \(p\). For example, \(C_{11} = \{3, 4\}\), because \(3,4,5\) are quadratic residues modulo 11 \(\big(5^2 \equiv 3, 2^2 \equiv 4, 4^2 \equiv 5 \pmod{11}\big).\)
It can be proven that \(C_p\) is non-empty for all \(p\). Let \(m_p\) be the smallest element of \(C_p\). Find the maximum value of \(m_p\) among all \(p\).
If this maximum doesn't exist, enter 0 as your answer.
Computing using Legendre Symbols
The last three properties taken together give a blueprint for an efficient computation of the Legendre symbol \( \left( \frac{a}{p} \right) \). Here are several examples of such computations.
Is \( 74 \) a quadratic residue mod \( 131?\)
Use the properties:
\[\begin{align} \left(\frac{74}{131}\right) &= \left(\frac{2}{131}\right) \left(\frac{37}{131}\right) \\ &= \left(\frac{2}{131}\right)\left(\frac{131}{37}\right) \\ &= \left(\frac{2}{131}\right)\left(\frac{20}{37}\right) \\ &= \left(\frac{2}{131}\right)\left(\frac{4}{37}\right)\left(\frac{5}{37}\right) \\ &= \left(\frac{2}{131}\right)\left(\frac{4}{37}\right)\left(\frac{37}{5}\right) \\ &= \left(\frac{2}{131}\right)\left(\frac{4}{37}\right)\left(\frac{2}{5}\right) \\\\ &= -1 \cdot 1 \cdot -1 = 1, \end{align}\]
where the last line is by the second supplement and the fact that \( 4 = 2^2 \), so the answer is yes. Indeed, \( 27^2 \equiv 74 \) mod \( 131 \), but notice that the Legendre symbol computation gives no information about the solutions to \( x^2 \equiv a \) mod \( p \) when they exist. \(_\square\)
This example shows the general strategy for computing using the Legendre symbol: factor the top as a product of primes, use Property 3 to separate into a product of Legendre symbols, compute the \( \left( \frac2{p} \right) \) symbols using Property 5, use Property 6 to flip the other Legendre symbols, and repeat. The process terminates, and relatively quickly (with a speed similar to the Euclidean algorithm).
One potential sticking point in this process is the factoring step, if the integers involved are large enough. In fact, there is a generalization of the Legendre symbol called the Jacobi symbol that eliminates the need to factor the numerator in these computations.
For which primes \( p \ge 5 \) is \( -3 \) a square mod \( p?\)
Compute
\[\begin{align} \left(\frac{-3}{p}\right) &= \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) \\ &= (-1)^{\frac{p-1}2} \cdot (-1)^{\frac{p-1}2} \left(\frac{p}{3}\right)\\ &= \left(\frac{p}{3}\right), \end{align}\]
which is \( 1 \) if and only if \( p \equiv 1 \) mod \( 3 \). So the answer is this: primes congruent to \( 1 \) mod \( 3 \). \(_\square\)