91Ó°ÊÓ

In number theory, a quadratic residue is a number that can be expressed as the square of another number modulo some integer. For instance, if we say "10 is a quadratic residue modulo 13", it means there exists an integer, say \( y \), such that \( y^2 \equiv 10 \mod 13\). Recognizing quadratic residues helps solve quadratic congruences, which are equations of the form \( x^2 \equiv a \mod m\). To determine if a given number is a quadratic residue with respect to a modulus \( p \) (usually a prime), we can use the **Legendre symbol** \( \left( \frac{a}{p} \right) \). This notation yields \( 1 \) if \( a \) is a quadratic residue modulo \( p \), and \( -1 \) if it's not. The process involves checking if \( a\) can be a perfect square under that modulus.
For more complex moduli, those which aren't prime, breaking them down into a product of prime factors allows us to determine the residue status individually for each prime factor.

Solving a quadratic congruence involves determining if there is an integer \( x \) that satisfies a congruence of the form \( x^2 \equiv a \mod m \). To evaluate solvability, we often break down the modulus into prime factors, especially when it's a composite number like 1105. This is essential due to the properties of quadratic residues, which can differ depending on the prime factors involved. In practice, we calculate whether \( a \), the number on the right-hand side of the congruence, is a quadratic residue for each prime factor. If \( a \) is not a residue for any of the factors, the congruence is unsolvable for the entire modulus. On the other hand, if \( a \) is a residue for all prime factors, solutions exist, and further analysis can help ascertain the specific solutions.

The Chinese Remainder Theorem (CRT) is a pivotal tool in number theory, especially for solving problems that involve congruences with moduli that share no common factors (i.e., they are coprime). It tells us how to find a solution to a series of congruences, each with a different prime factor as the modulus. In the context of quadratic congruences, CRT provides a way to integrate the solvability results from each prime factor modulus back into a solution or, as in this case, to conclude the congruence's overall solvability or unsolvability.
For instance, if a number is a quadratic residue not across all components, the CRT implies the original modulus' congruence equation is unsolvable. This is because CRT ensures there is a one-to-one relationship between solving modulo a composite number and solving modulo its individual prime factors, but only when residue conditions are uniform.

Euler's Criterion is a powerful method for checking whether a number is a quadratic residue modulo a prime. For an odd prime \( p \) and any integer \( a \) coprime to \( p \), Euler's Criterion states that \( a \) is a quadratic residue modulo \( p \) if \( a^{(p-1)/2} \equiv 1 \mod p \), and a non-residue if the equivalence is \( -1 \). This criterion simplifies the use of quadratic reciprocity laws by providing a straightforward calculation. In practice, applying Euler's Criterion requires basic modular arithmetic. It simplifies examining quadratic residuosity, especially when a direct determination might be difficult.

• First, compute \( a^{(p-1)/2} \mod p \).
• Then, check the result: \( 1 \) indicates a residue, while \( -1 \) indicates a non-residue.

Euler's Criterion provides a quick check for each prime factor in the factorization of a composite modulus, helping to understand the solubility of the quadratic congruences.