Quadratic Congruences

Dušan Đukić

Introduction

Quadratic congruences are of the form \( x^2\equiv a \) (mod \( n \)). Some of them have, and some of them don’t have solutions. The Legendre and Jacobi symbols are objects developed to simplify understanding of solvability of quadratic congruences. The Gauss reciprocity law enables us to easily evaluate these symbols and thus provide us with tools to determine whether the equations have solutions.

In this article we discuss basic and advanced properties of these symbols and show how the theory of quadratic residues is applied in Diophantine equations and other types of problems that can hardly be solved otherwise. No knowledge on advanced number theory is presumed.

Table of Contents

Quadratic congruences to prime moduli

Quadratic congruences to composite moduli

Some sums of Legendre’s symbols

Problems