Neliöresidujen

Neliöresidujen, also known as quadratic residues, are a fundamental concept in number theory. An integer a is a quadratic residue modulo n if there exists an integer x such that x^2 is congruent to a modulo n. In simpler terms, a is a quadratic residue modulo n if it is the remainder when a perfect square is divided by n. If no such integer x exists, then a is called a quadratic non-residue modulo n.

The study of quadratic residues is primarily concerned with determining whether a given integer is a quadratic residue for a specific modulus. For prime moduli, especially odd primes, the properties of quadratic residues are well-understood. For example, modulo an odd prime p, exactly half of the non-zero residues are quadratic residues, and the other half are quadratic non-residues. The Legendre symbol is a notation used to compactly represent whether an integer is a quadratic residue modulo a prime.

The concept extends to composite moduli, although the analysis becomes more complex, often involving the Chinese Remainder Theorem and the properties of quadratic residues modulo prime powers. Quadratic residues play a significant role in various areas of mathematics, including cryptography (e.g., the Rabin cryptosystem) and the theory of Diophantine equations. Understanding their distribution and properties is a key aspect of number theoretic investigations.