91Ó°ÊÓ

An odd prime is a prime number greater than 2, as 2 is the only even prime. Examples of odd prime numbers include 3, 5, 7, 11, and so on. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This makes the properties of odd primes very useful in number theory, including modular arithmetic and quadratic congruences. When dealing with congruences, odd primes help simplify the problem, especially when analyzing solutions to equations like \(x^2 \equiv a (\bmod p)\).

A quadratic residue modulo \( p \) is an integer \( a \) such that there exists an integer \( x \) satisfying the congruence \( x^2 \equiv a \bmod p \). This means that when \( x \) is squared and divided by \( p \), the remainder is \( a \).
There are specific properties for quadratic residues:

• If \( a ot\equiv 0 \bmod p \), then \( a \) is a quadratic residue modulo \( p \) if there exists an integer \( x \) that solves the equation \( x^2 \equiv a \bmod p \).
• If such an \( x \) exists, there are exactly two distinct solutions modulo \( p \) to the equation \( x^2 \equiv a \bmod p \), corresponding to \( x \) and \( -x \).

If \( a \) is not a quadratic residue modulo \( p \), there are no solutions to the equation \( x^2 \equiv a \bmod p \). This distinction between having zero or two solutions is crucial for understanding quadratic congruences.

The Legendre symbol \( (\frac{a}{p}) \) is a mathematical notation used to determine whether a given number \( a \) is a quadratic residue modulo an odd prime number \( p \).
It is defined as:
\begin{cases} \ 1 &\text{if } a \text{ is a quadratic residue modulo } p \;-1 &\text{if } a \text{ is not a quadratic residue modulo } p \;0 &\text{if } a \equiv 0 \bmod p \end{cases}
To find this, you need to interpret the congruence equation and determine whether a solving \( x \) exists for \( x^2 \equiv a \).
This makes the Legendre symbol a simple yet powerful tool for solving quadratic congruences. For example, if \( (\frac{a}{p}) = 1 \), we know there are exactly two incongruent solutions modulo \( p \), while \( (\frac{a}{p}) = -1 \) implies no solutions.

The concept of modulo, often represented as \( \bmod \), is fundamental in number theory, particularly in modular arithmetic. Modulo operation finds the remainder of division of one number by another. For two integers \( a \) and \( n \), we write
\ a \equiv b (\bmod n) \ when \( b \) is the remainder when \( a \) is divided by \( n.\)
For example, \( 10 \equiv 1 (\bmod 3) \) because 10 divided by 3 leaves a remainder of 1. When dealing with quadratic congruences, understanding modulo helps simplify number properties. It allows us to determine if certain equations have solutions and how many solutions exist.