CorollaryStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

$x^{2} \equiv a (m o d p)$ has exactly $1 + (a / p)$ solution classes

Statement

For every integer $a$ and odd prime $p$ , the congruence

$x^{2} \equiv a (m o d p)$

has exactly $1 + (a / p)$ solution classes modulo $p$ .

Facts & Assumptions

Given: An integer $a$ and an odd prime $p$ .

[L1]

The Legendre symbol is $0$ when $p ∣ a$ , $1$ when $a$ is a quadratic residue modulo $p$ , and $- 1$ when $a$ is a quadratic nonresidue (The Legendre symbol, including its zero value).

[L2]

The quotient $Z / p$ is a field (For every prime $p$ , the two operations on $Z / p$ make it a field).

[L3]

Every field is an integral domain (Every field is a commutative ring with $1 \neq 0$ ; it is an integral domain, and it is a commutative division ring).

[L4]

Under its primitive-root, coprimality, positivity, and solubility hypotheses, $x^{m} \equiv a (m o d n)$ has exactly $\gcd (φ (n), m)$ solution classes (If $n$ has a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly $\gcd (φ (n), m)$ solution classes modulo $n$ ).

[L5]

Every prime admits a primitive root modulo that prime (Every prime modulus admits a primitive root).

[L6]

For every prime $p$ , $φ (p) = p - 1$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L7]

If $p ∤ a$ , then $p$ and $a$ are coprime (For a prime $p$ and any integer $a$ , $\gcd (p, a)$ is $p$ when $p ∣ a$ and $1$ otherwise; so $p ∤ a$ makes $p$ and $a$ coprime).

Proof

technique · direct

1.1

If $p ∣ a$ , the equation in the field [L2] is $[x]_{p}^{2} = [0]_{p}$ . Since [L3] gives no zero divisors, $[x]_{p} = [0]_{p}$ is the unique solution. This count is $1 + 0$ by [L1].

L1L2L3given

1.2

Suppose $p ∤ a$ . By [L7], $\gcd (a, p) = 1$ . If $(a / p) = 1$ , the congruence is soluble by [L1], and [L4], [L5], and [L6] give exactly $\gcd (p - 1, 2) = 2$ roots. If $(a / p) = - 1$ , [L1] says that no root exists.

L1L4L5L6L7algebra

2.1

The three possible symbol values $0, 1, - 1$ therefore give respectively one, two, and zero solution classes, which in every case equals $1 + (a / p)$ .

L1step 1.1step 1.2∎

Depends on

Used by

The discriminant counts roots of Ax²+Bx+C≡0 pmod p for odd prime p∤ A Corollary
A soluble square congruence need not define a quadratic residue Counterexample

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 101 results over 24 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

W. Stein, Elementary Number Theory, Corollary 4.2.3 (standard reference, not scraped)
A. Gorodnik, Number Theory, Lecture 9, Section 1 (standard reference, not scraped)

x2≡a(modp)x2≡a(modp) has exactly 1+(a/p)1+(a/p) solution classes