Orders and quadratic residues · Definition

Legendre symbol

elementary number theoryorders and quadratic residues

Before you start you need to know

The Legendre symbol condenses into a single value whether a residue class is a square modulo a prime. It is the central tool for deciding solvability of \(x^2\equiv a \pmod p\).

Definition

The Legendre symbol \(\left(\frac{a}{p}\right)\) for an odd prime \(p\) and an integer \(a\) with \(p \nmid a\) equals \(1\) if \(a\) is a quadratic residue modulo \(p\), and \(-1\) if it is not.

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

Euler's criterion states that \(\left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \pmod p\), from which one derives multiplicativity \(\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\) and dependence only on the class of \(a\) modulo \(p\). Consequently, exactly half of the nonzero classes modulo \(p\) are quadratic residues.

For \(p=7\) the nonzero squares are \(1,2,4\), so \(\left(\frac{3}{7}\right)=-1\) because \(3\) is not in that list, while \(\left(\frac{9}{7}\right)=\left(\frac{2}{7}\right)=1\) after reducing \(9\equiv 2\pmod 7\). Evaluating the symbol on \(a\) without first reducing modulo \(p\) is a common source of error.

A typical mistake is forgetting that the symbol is defined only when \(p\nmid a\), or assuming that \(\left(\frac{a}{p}\right)=-1\) means \(a\) is negative. The value depends only on the class of \(a\) modulo \(p\), and the sign of \(a\) as an integer plays no role.

Think about it

Does the Legendre symbol depend on the sign of \(a\) as an integer, or only on its class modulo \(p\)?

Only on its class modulo \(p\); the sign of \(a\) as an integer plays no role.

Exercises 10

  1. What is the value of \(\left(\frac{4}{11}\right)\)?
  2. What is the value of \(\left(\frac{-1}{5}\right)\)?
  3. If \(p\) is an odd prime and \(p\mid a\), what is \(\left(\frac{a}{p}\right)\)?
  4. According to Euler's criterion, what is \(a^{(p-1)/2}\) congruent to modulo \(p\) when \(p\nmid a\)?
  5. What is the value of \(\left(\frac{2}{3}\right)\)?
  6. Compute \(\left(\frac{10}{13}\right)\) given that the nonzero squares modulo 13 are \(1,4,9,3,12,10\).
  7. Compute \(\left(\frac{3}{7}\right)\cdot\left(\frac{5}{7}\right)\).
  8. Compute \(\left(\frac{2}{p}\right)\) for \(p=17\) using that \(6^2\equiv 2\pmod{17}\).
  9. Using Euler's criterion, compute \(2^{3}\bmod 7\) and state which symbol \(2\) represents modulo 7.
  10. Give a counterexample showing that \(\left(\frac{a+b}{p}\right)=\left(\frac{a}{p}\right)+\left(\frac{b}{p}\right)\) fails in general, taking \(p=7\), \(a=1\), \(b=2\).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 9
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 3