LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-17

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.

Gauss's lemma as a lower-half lattice-point count

Statement

Let $p$ and $q$ be distinct odd primes. Put $S_{p, q} : = ∣ {(x, y) \in Z^{2} : 1 \leq x \leq (p - 1) / 2, 0 < p y < q x} ∣$ .

Then $(\frac{q}{p}) = (- 1)^{S_{p, q}}$ .

Thus Gauss's sign count (Gauss's quadratic-residue lemma) can be read as the parity of a finite set of lattice points, without introducing floor notation.

Facts & Assumptions

Given: Distinct odd primes $p, q$ , and $m = (p - 1) / 2$ .

[L1]

If $N (q, p)$ is the number of least positive residues of $q, 2 q, \dots, m q$ modulo $p$ that exceed $p / 2$ , then $(\frac{q}{p}) = (- 1)^{N (q, p)}$ (Gauss's quadratic-residue lemma).

[L2]

For every integer $A$ and positive integer $p$ , there are unique integers $t, ρ$ such that $A = p t + ρ$ and $0 \leq ρ < p$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L3]

For each $1 \leq x \leq m$ , there are unique $ε_{x} \in {1, - 1}$ and $u_{x} \in {1, \dots, m}$ such that $q x \equiv ε_{x} u_{x} (m o d p)$ , and $u_{1}, \dots, u_{m}$ is a permutation of $1, \dots, m$ (Multiplication by $a$ with $p ∤ a$ permutes an odd prime's signed half-system up to sign).

Proof

technique · direct

1.1

For each $1 \leq x \leq m$ , [L2] gives $q x = p t_{x} + ρ_{x}$ with $0 \leq ρ_{x} < p$ ; since $p ∤ q x$ , one has $0 < ρ_{x} < p$ . The positive integers $y$ satisfying $p y < q x = p t_{x} + ρ_{x}$ are exactly $1, \dots, t_{x}$ , so $S_{p, q} = \sum_{x = 1}^{m} t_{x}$ .

L2givenalgebra

2.1

In the notation of [L3], $ρ_{x} = u_{x}$ when $ε_{x} = 1$ and $ρ_{x} = p - u_{x}$ when $ε_{x} = - 1$ ; the negative signs are exactly the residues counted by $N (q, p)$ . Summing the equations of step 1.1 and reducing modulo $2$ gives $\sum_{x} x \equiv S_{p, q} + \sum_{x} ρ_{x} (m o d 2)$ , because $p$ and $q$ are odd. Also $\sum_{x} ρ_{x} \equiv \sum_{x} u_{x} + N (q, p) (m o d 2)$ , while the permutation in [L3] gives $\sum_{x} u_{x} = \sum_{x} x$ . Hence $S_{p, q} \equiv N (q, p) (m o d 2)$ , and [L1] yields $(\frac{q}{p}) = (- 1)^{S_{p, q}}$ .

step 1.1L1L3algebra∎

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 78 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

P. Hackman, Elementary Number Theory, §D.V (standard reference, not scraped)
A. Gorodnik, Number Theory, Lecture 9, §2 (standard reference, not scraped)