O'Reilly logo

A Comprehensive Course in Number Theory by Alan Baker

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

4

Quadratic residues

4.1 Legendre’s symbol

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

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 x2a (mod n) is soluble; otherwise it is called a quadratic non-residue (mod n). The Legendre symbol (image), where p is a prime and (a, p) = 1 is defined as 1 if ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required