A quadratic residue modulo m is an integer a for which the quadratic congruence x^2 ≡ a (mod m) has a solution. The seemingly simple question of which integers are quadratic residues modulo a given integer leads to an extensive theory and a broad range of applications. This master's thesis focuses on quadratic congruences and quadratic residues, with particular emphasis on the Law of Quadratic Reciprocity, which reveals an important relationship between quadratic residues. The Legendre symbol, Euler's criterion and Gauss's lemma are introduced as tools to determine the quadratic nature of integers modulo an odd prime. Quadratic reciprocity is proved using Zolotarev's lemma, which establishes a connection between quadratic residues and permutations. The use of the Jacobi symbol then extends our discussion from prime to composite moduli. Conditions for solvability of quadratic congruences and the number of their solutions for different types of moduli are also presented. The final part discusses several applications, including primality tests such as the Solovay-Strassen probabilistic primality test and Pépin's test as well as Blum's cryptographic protocol for coin flipping by telephone. The usefulness of the presented results is further illustrated through selected problems from international mathematical competitions.
|
