Legendre Symbol and Its Properties

Number Theory

1. Divisibility
- 1.1. Greatest Common Divisor
  - 1.1.1. Important Problems On Greatest Common Divisor
- 1.2. Expressing Cubes As Differences Of Squares
2. Prime Numbers
- 2.1. Important Problems On Prime Numbers
- 2.2. Prime Number Theorem
  - 2.2.1. The Prime Number Theorem Explained With Interpretation
3. Congruence
- 3.1. Linear Congruence
  - 3.1.1. Important Applications On Linear Congruence
4. Number Theoretic Functions
- 4.1. Greatest Integer Functions
  - 4.1.1. Divisibility Of Binomial Coefficients
5. Quadratic Reciprocity
- 5.1. Legendre Symbol
  - 5.1.1. Legendre Symbol And Its Properties
6. Fermats Last Theorem
- 6.1. Proof Of Fermats Last Theorem
- 6.2. Pythagorean Triples
  - 6.2.1. Important Problems On Pythagorean Triples
7. Integers As Sum Of Squares
- 7.1. Sum Of More Than Two Squares
  - 7.1.1. Representation Of Integers As Sums Of Five Nonzero Squares For All Values Greater Than Or Equal To 170
- 7.2. Sum Of Two Squares
  - 7.2.1. Perfect Squares In Pythagorean Triples
8. Encryption And Decryption
- 8.1. Linear Cipher
  - 8.1.1. Important Applications On Linear Cipher
- 8.2. Hill Cipher
  - 8.2.1. Hill Cipher Decryption In Number Theory Step By Step With Example

Tags

Legendre Symbol

Legendre Symbol and Its Properties is a core topic in Number Theory, used to determine whether a number is a quadratic residue modulo a prime. This section covers the definition and essential properties of the Legendre Symbol, including its behavior under multiplication, its values, and its role in the law of quadratic reciprocity. With simple explanations, solved examples, and practical applications, this guide helps students understand both the concept and the logic behind the Legendre Symbol and Its Properties, making it ideal for academic and competitive exam preparation.

Legendre Symbol

Let \( p \) be an odd prime and let \( a \) be an integer such that \( \gcd(a, p) = 1 \). The Legendre Symbol is defined as

\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p, \\ -1 & \text{if } a \text{ is a quadratic nonresidue modulo } p. \end{cases}

Properties

Properties of the Legendre Symbol

Let \( p \) be an odd prime and \( a, b \in \mathbb{Z} \) such that \( \gcd(a, p) = \gcd(b, p) = 1 \). Then the Legendre Symbol satisfies the following properties:

If \( a \equiv b \pmod{p} \), then \( \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right) \).
\( \left( \frac{a^2}{p} \right) = 1 \).
\( \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p} \) (Euler's Criterion).
\( \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \).
\( \left( \frac{1}{p} \right) = 1 \) and \( \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} \).

(1) Congruence Property:

If \( a \equiv b \pmod{p} \), then \( a \) and \( b \) leave the same remainder modulo \( p \). Hence, they have the same quadratic residue status modulo \( p \), so:

\left( \frac{a}{p} \right) = \left( \frac{b}{p} \right).

(2) Square is Residue:

Let \( a \) be relatively prime to \( p \). Then \( a^2 \equiv r \pmod{p} \) for some \( r \). Since \( a^2 \) is the square of an integer not divisible by \( p \), it is clearly a quadratic residue. So:

\left( \frac{a^2}{p} \right) = 1.

(3) Euler's Criterion:

Euler's Criterion states:

\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}.

This follows from Fermat’s Little Theorem and properties of primitive roots. The proof is standard in number theory and confirms the symbolic relationship using modular exponentiation.

(4) Multiplicativity:

Let \( a, b \in \mathbb{Z} \) with \( \gcd(ab, p) = 1 \). Then,

\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right).

This follows from Euler's Criterion and the fact that:

(ab)^{\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} b^{\frac{p-1}{2}} \pmod{p}.

(5) Values at \( \pm 1 \):

We compute:

\left( \frac{1}{p} \right) = 1, \quad \text{since } 1^2 \equiv 1 \pmod{p}.

By definition of Legendre Symbol and modular parity

\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}

This tells us that \( -1 \) is a quadratic residue modulo \( p \) if and only if \( p \equiv 1 \pmod{4} \).

Find the value of the Legendre Symbol

\left( \frac{-23}{59} \right)

We use the identity:

\left( \frac{-23}{59} \right) = \left( \frac{-1}{59} \right) \cdot \left( \frac{23}{59} \right)

We know that

\left( \frac{-1}{59} \right) = (-1)^{\frac{59 - 1}{2}} = (-1)^{29} = -1

Using Euler’s Criterion

\left( \frac{23}{59} \right) \equiv 23^{29} \pmod{59}

Compute using repeated squaring:

\begin{align*} & 23^2 \equiv 57 \pmod{59} \\ & 23^4 \equiv 4 \pmod{59} \\ & 23^8 \equiv 16 \pmod{59} \\ & 23^{16} \equiv 20 \pmod{59} \end{align*}

Therefore

\begin{align*} 23^{29} &\equiv 20 \cdot 16 \cdot 4 \cdot 23 \equiv 25 \cdot 4 \cdot 23 \\ &\equiv 100 \cdot 23 \equiv 41 \cdot 23 \equiv -1 \pmod{59} \end{align*}

\Rightarrow \left( \frac{23}{59} \right) = -1

Hence

\left( \frac{-23}{59} \right) = (-1)(-1) = \boxed{1}