Orders and quadratic residues · Definition

Euler's criterion

elementary number theoryorders and quadratic residues

Before you start you need to know

Euler's criterion turns the question about quadratic residues into a power computation. It relies on the Legendre symbol and on Fermat's little theorem.

Definition

Criterion that decides whether an integer \(a\) is a quadratic residue modulo an odd prime \(p\) by means of a modular power.

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

For an odd prime \(p\) and an integer \(a\) with \(p\nmid a\), the Legendre symbol equals 1 or -1, and the modular power takes exactly these two values. This gives a residue test without listing all the squares.

Take \(p=7\) and \(a=3\). Since \(3^{3}=27\equiv -1\pmod 7\), the symbol equals -1 and 3 is not a quadratic residue modulo 7. In contrast, \(2^{3}\equiv 1\pmod 7\), so 2 is a residue.

A common mistake is to use the exponent \(p-1\) instead of \((p-1)/2\), which always gives 1 and cannot distinguish residues. The criterion also does not apply when \(p\mid a\), where the symbol equals 0.

Think about it

Why does the criterion use \((p-1)/2\) instead of \(p-1\)?

Because \(a^{p-1}\equiv 1\pmod p\) by Fermat for every \(a\) with \(p\nmid a\), so it cannot distinguish residues.

Exercises 10

  1. According to Euler's criterion, what is \(\left(\frac{a}{p}\right)\) congruent to modulo \(p\)?
  2. For \(p=11\), which exponent \((p-1)/2\) does the criterion use?
  3. For which primes \(p\) does Euler's criterion hold as stated in this sheet?
  4. If \(a\) is a quadratic residue modulo \(p\), what is the value of \(a^{(p-1)/2}\bmod p\)?
  5. If \(a^{(p-1)/2}\equiv -1\pmod p\), what can you conclude about \(a\)?
  6. Use the criterion to decide whether 3 is a quadratic residue modulo 7. What is the correct conclusion?
  7. For \(p=13\) and \(a=5\), what is \(5^{6}\bmod 13\), and what does it mean?
  8. What is \(2^{(5-1)/2}\bmod 5\), and what does it indicate about \(2\)?
  9. If \(a^{(p-1)/2}\equiv 1\pmod p\) and \(b^{(p-1)/2}\equiv 1\pmod p\), what is \((ab)^{(p-1)/2}\) congruent to modulo \(p\)?
  10. Which of these claims is false?

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