4

Quadratic residues

**4.1 Legendre’s symbol**

In the last chapter we discussed the linear congruence *ax* ≡ *b* (mod *n*). Here we shall study the quadratic congruence *x*^{2} ≡ *a* (mod *n*); in fact this amounts to the study of the general quadratic congruence *ax*^{2} + *bx* + *c* ≡ 0 (mod *n*), since on writing *d* = *b*^{2} − 4*ac* and *y* = 2*ax* + *b*, the latter gives *y*^{2} ≡ *d* (mod 4*an*).

Let *a* be any integer, let *n* be a natural number and suppose that (*a*, *n*) = 1. Then *a* is called a quadratic residue (mod *n*) if the congruence *x*^{2} ≡ *a* (mod *n*) is soluble; otherwise it is called a quadratic non-residue (mod *n*). The Legendre symbol (), where *p* is a prime and (*a*, *p*) = 1 is defined as 1 if ...

Start Free Trial

No credit card required