Quadratic residue

Mathematical statement

Normalize a into0,...,p−1 first. The zero class is handled separately and is not called a nonzero quadratic residue. For odd prime p, every nonzero residue has two distinct opposite roots x and −x. Do not silently include p=2, composite moduli or zero. Euler criterion and the Legendre symbol are not assumed in this node.

Representative formula (exact TeX)

Q(a,p)

Assumptions

• Main families enumerate every square of x=1,...,p−1.
• p is a bounded odd prime and a is a safe integer.

Symbol scope

• Q — quadratic-residue predicate
• a — normalized residue candidate
• p — odd-prime modulus

Intuition, definition, and misconceptions

The complete nonzero square table decides membership.

Roots pair as x and −x.

Zero, even-prime and composite boundaries remain separate.

Do not count0 among nonzero residues or transfer the two-root conclusion unchanged to composite moduli.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Natural-number congruence modulo a positive modulus — Use square congruence.
• Prime natural number — The domain requires an odd prime.
• Natural-number powers and principal square roots — The operation is squaring.

Verification boundary

Euler criterion and the Legendre symbol are reserved for later nodes.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add the Legendre symbol.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.