Quadratic Residues

🔐 The Secret Code of Perfect Squares: Quadratic Residues

Imagine you have a magical machine. You put in any number, square it, and divide by a special number. The leftover (remainder) tells you a secret about that number. That’s quadratic residues!

🎯 What Are Quadratic Residues?

Think of it like a secret club. Some numbers can get in, others can’t.

Here’s the rule: A number a is a quadratic residue modulo p if you can find some number that, when squared and divided by p, leaves remainder a.

Simple Example

Let’s say our special number is 7.

The quadratic residues mod 7 are: {1, 2, 4}

The non-residues are: {3, 5, 6} — No perfect square gives these remainders!

🌟 Key Insight: For any odd prime p, exactly half the numbers (1 to p-1) are quadratic residues!

🧮 Computing Residues: The Detective Work

How do we find if a number is a quadratic residue without checking every square?

The Euler Criterion — Your Magic Wand 🪄

The Rule: For an odd prime p and a number a not divisible by p:

a^((p-1)/2) ≡ 1 (mod p)  → a IS a quadratic residue
a^((p-1)/2) ≡ -1 (mod p) → a is NOT a quadratic residue

Example: Is 2 a quadratic residue mod 7?

p = 7, a = 2
(p-1)/2 = 3

Calculate: 2³ = 8
8 mod 7 = 1 ✓

Since we got 1, YES! 2 is a quadratic residue mod 7!

Example: Is 3 a quadratic residue mod 7?

3³ = 27
27 mod 7 = 6 = -1 (mod 7)

Since we got -1, NO! 3 is NOT a quadratic residue mod 7!

📊 The Legendre Symbol — A Simple Yes/No Badge

Instead of writing “is a quadratic residue,” mathematicians use a cute symbol.

graph TD
    A["#40;a/p#41; = ?"] --> B{Is a ≡ 0 mod p?}
    B -->|Yes| C["#40;a/p#41; = 0"]
    B -->|No| D{Is a a QR mod p?}
    D -->|Yes| E["#40;a/p#41; = +1"]
    D -->|No| F["#40;a/p#41; = -1"]

The Legendre Symbol (a/p):

Examples with p = 11:

• (1/11) = +1 → 1² = 1, so 1 is a QR ✓
• (3/11) = +1 → 5² = 25 ≡ 3 (mod 11) ✓
• (2/11) = -1 → No perfect square gives 2 mod 11 ✗
• (11/11) = 0 → 11 divides 11

Multiplication Property 🎁

The Legendre symbol is multiplicative:

(ab/p) = (a/p) × (b/p)

Example: (6/7) = (2/7) × (3/7) = (+1) × (-1) = -1

🔧 The Jacobi Symbol — Legendre’s Big Brother

What if p isn’t prime? Enter the Jacobi symbol!

For any odd number n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ:

(a/n) = (a/p₁)^e₁ × (a/p₂)^e₂ × ... × (a/pₖ)^eₖ

Example: Calculate (2/15)

15 = 3 × 5

(2/15) = (2/3) × (2/5)
       = (-1) × (-1)
       = +1

⚠️ Important Warning!

Jacobi = +1 does NOT always mean quadratic residue!

It only tells us maybe — we need more checks for composite numbers.

Jacobi Symbol Properties

1. (1/n) = 1 always
2. (a/n) = 0 if gcd(a,n) > 1
3. (ab/n) = (a/n)(b/n) — multiplicative
4. (a/mn) = (a/m)(a/n) — also multiplicative in bottom

👑 Quadratic Reciprocity — The Crown Jewel

This is the most beautiful theorem in number theory. Gauss called it the “Golden Theorem”!

graph TD
    A["Two odd primes: p and q"] --> B["Question: How are #40;p/q#41; and #40;q/p#41; related?"]
    B --> C{"Is p ≡ 1 OR q ≡ 1 #40;mod 4#41;?"}
    C -->|Yes| D["#40;p/q#41; = #40;q/p#41;<br>They're the SAME!"]
    C -->|No| E["p ≡ q ≡ 3 #40;mod 4#41;"]
    E --> F["#40;p/q#41; = -#40;q/p#41;<br>They're OPPOSITE!"]

The Law of Quadratic Reciprocity

For distinct odd primes p and q:

(p/q) × (q/p) = (-1)^((p-1)/2 × (q-1)/2)

In plain English:

• If p ≡ 1 (mod 4) OR q ≡ 1 (mod 4): (p/q) = (q/p)
• If p ≡ 3 (mod 4) AND q ≡ 3 (mod 4): (p/q) = -(q/p)

Example: Find (3/11)

p = 3, q = 11

3 ≡ 3 (mod 4)
11 ≡ 3 (mod 4)

Both ≡ 3, so (3/11) = -(11/3)

Now: 11 mod 3 = 2
So: (11/3) = (2/3)

Using special rule for 2:
(2/3) = (-1)^((9-1)/8) = (-1)^1 = -1

Therefore: (3/11) = -(-1) = +1 ✓

The Supplements — Special Cases for -1 and 2

First Supplement — The (-1) Rule:

(-1/p) = +1  if p ≡ 1 (mod 4)
(-1/p) = -1  if p ≡ 3 (mod 4)

Second Supplement — The (2) Rule:

(2/p) = +1  if p ≡ 1 or 7 (mod 8)
(2/p) = -1  if p ≡ 3 or 5 (mod 8)

Complete Example: Calculate (35/97)

Step 1: Factor 35 = 5 × 7
(35/97) = (5/97) × (7/97)

Step 2: Find (5/97) using reciprocity
5 ≡ 1 (mod 4), so (5/97) = (97/5)
97 mod 5 = 2
(97/5) = (2/5)
5 ≡ 5 (mod 8), so (2/5) = -1
∴ (5/97) = -1

Step 3: Find (7/97) using reciprocity
7 ≡ 3 (mod 4), 97 ≡ 1 (mod 4)
At least one ≡ 1, so (7/97) = (97/7)
97 mod 7 = 6 = -1 (mod 7)
(97/7) = (-1/7)
7 ≡ 3 (mod 4), so (-1/7) = -1
∴ (7/97) = -1

Step 4: Combine!
(35/97) = (-1) × (-1) = +1 ✓

🎯 Quick Reference Table

🌈 Why Does This Matter?

1. Cryptography — RSA and many encryption systems use quadratic residues
2. Primality Testing — Helps determine if huge numbers are prime
3. Solving Equations — Tells us when x² = a (mod p) has solutions
4. Pure Beauty — The reciprocity law shows deep symmetry in math

🚀 Key Takeaways

1. Quadratic residues = remainders you can get from perfect squares
2. Computing residues = Use Euler’s criterion (raise to power (p-1)/2)
3. Legendre symbol = Simple +1, -1, 0 notation for primes
4. Jacobi symbol = Extended to composite numbers (multiply Legendres)
5. Quadratic reciprocity = Magical relationship between (p/q) and (q/p)

💡 “Mathematics is not about numbers, equations, or algorithms: it is about understanding.” — William Paul Thurston

You now hold one of the most elegant keys in all of mathematics. The Law of Quadratic Reciprocity took Gauss himself eight proofs to fully explore. You’ve just learned what took him years to perfect! 🎉