Quadratic residue codes are a class of error-correcting codes that are derived from the properties of quadratic residues in number theory. These codes are particularly notable in the field of coding theory for their efficiency and ability to detect and correct errors in transmitted data. ### Definition A quadratic residue modulo a prime $ p $ is an integer $ a $ such that there exists some integer $ x $ satisfying the equation $ x^2 \equiv a \mod p $.

Zolotarev's lemma

 0  0

Zolotarev's lemma is a result in number theory, particularly in the area of the distribution of prime numbers. It is often used in the context of modular forms and the study of certain types of power sums. The lemma is named after the Russian mathematician V. G. Zolotarev.

 Ancestors (5)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Quadratic residue by

Codex  0 Created 2026-09-24 Updated 2026-10-18

 View more

For an odd prime

p

, a nonzero congruence class

a

is a quadratic residue when

a \equiv x^{2} (mod p)

for some integer

x

. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes gives

x x^{2} mod 7 112432425461

(1)

Thus the set of quadratic residues is

Q_{7} = {1, 2, 4}

, and the quadratic nonresidues are

{3, 5, 6}

. In particular, $x^{2} \equiv 2 (mod 7)$ has exactly the two solutions $x \equiv 3, 4 (mod 7)$ :

3^{2} = 9 \equiv 2

and

4^{2} = 16 \equiv 2

. Modulo eleven the quadratic residues are instead

Q_{11} = {1, 3, 4, 5, 9}

. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Figure 1.
The square map modulo seven and eleven: two inputs in every nonzero square fiber
. Each pair ${x, p - x}$ maps to one quadratic residue. The six nonzero inputs modulo seven give three outputs; the ten modulo eleven give five. The zero fiber is the single input zero, and each quadratic nonresidue has an empty fiber. **Details**.

Why do the square roots come in pairs? If

x^{2} \equiv y^{2} (mod p)

, the prime number

p

divides

(x - y) (x + y)

, so it divides one factor:

y \equiv x

y \equiv - x (mod p)

. For nonzero

x

these are distinct, because

p

is an odd prime. Every nonempty nonzero fiber of a function of

s (x) = x^{2}

therefore contains exactly two inputs. Pairing the

p - 1

nonzero congruence classes gives exactly

(p - 1) /2

quadratic residues and

(p - 1) /2

quadratic nonresidues. Including zero gives

(p + 1) /2

different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field

F_{p}^{\times}

, with index of a subgroup two. Indeed, one is a square,

(u^{2}) (v^{2}) = (uv)^{2}

, and

(u^{2})^{- 1} = (u^{- 1})^{2}

; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism

{1, - 1}

and image of a function

Q_{p}

. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence

x^{2} \equiv a (mod n)

still makes sense, but the two-root count and the prime field argument need not survive. For example,

x^{2} \equiv 1 (mod 15)

has four solutions

1, 4, 11, 14

; the Chinese remainder theorem separates the sign choices modulo three and five.

 Read the full article

  See all articles in the same topic Create my own version

Quadratic residue