The Legendre Symbol

Number Theory · Axiom Academy

A compact notation for quadratic residuosity modulo prime numbers 1. Definition of the Legendre Symbol Let p be an odd prime and a be any integer. The Legendre symbol (a/p) is defined as follows: (a/p) = 1 if a is a quadratic residue modulo p and a is not divisible by p (a/p) = -1 if a is a quadratic non-residue modulo p Let's compute several Legendre symbols to understand how they work in practice. We'll use p = 7 and test various values of a . For multiples of 7, the symbol equals 0 For quadratic residues (1, 2, 4), the symbol equals +1 For non-residues (3, 5, 6), the symbol equals -1 The Legendre symbol has several important properties that make it a powerful computational tool: Multiplicativity: (ab/p) = (a/p)(b/p) Congruence: If a ≡ b (mod p), then (a/p) = (b/p) Euler's Criterion: (a/p) ≡ a^((p-1)/2) (mod p) Special values: (1/p) = 1 and (-1/p) = (-1)^((p-1)/2) Euler's Criterion is particularly useful because it gives us a computational method: we can evaluate the Legendre symbol by computing a power modulo p . 4. Applications and Importance The Legendre symbol is fundamental to many areas of number theory and has practical applications in cryptography and coding theory. Quadratic Reciprocity: The Legendre symbol is essential for stating and proving the law of quadratic reciprocity, one of the most beautiful theorems in number theory Primality Testing: Euler's criterion can be used in probabilistic primality tests

This is the written version of the interactive lesson above. See the full Number Theory course.