LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

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.

A square is congruent to $0$ , $1$ or $4$ modulo $8$

Statement

Call an integer even when $2$ divides it and odd otherwise (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). Let $x \in Z$ . Then $x^{2}$ is congruent to $0$ , to $1$ or to $4$ modulo $8$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ). More precisely, if $x$ is odd then $x^{2} \equiv 1 (m o d 8)$ , and if $x$ is even then $x^{2} \equiv 0 (m o d 8)$ or $x^{2} \equiv 4 (m o d 8)$ .

Consequently, if $x$ is odd then $x^{2} \equiv 1 (m o d 4)$ , and if $x$ is even then $x^{2} \equiv 0 (m o d 4)$ .

Facts & Assumptions

Given: An integer $x$ .

[F1]

For $a, b, n \in Z$ , $a \equiv b (m o d n)$ means $n ∣ (a - b)$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

[F2]

For $d, a \in Z$ , $d ∣ a$ means $a = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L1]

For $a, b \in Z$ with $b \neq 0$ there is exactly one pair $(q, r)$ of integers with $a = q b + r$ and $0 \leq r < ∣ b ∣$ ; moreover $b ∣ a$ holds exactly when $r = 0$ (Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$ ).

[L2]

Let $a$ be odd. For $k \geq 3$ , the congruence $x^{2} \equiv a (m o d 2^{k})$ is soluble if and only if $a \equiv 1 (m o d 8)$ (Unit square criterion and root count modulo powers of two).

[L3]

Divisibility is transitive: $d ∣ a$ and $a ∣ b$ imply $d ∣ b$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

Proof

technique · cases

1.1

By [L1] with $b = 2$ there is exactly one pair $(q, r)$ with $x = 2 q + r$ and $0 \leq r < 2$ , so $r = 0$ or $r = 1$ ; that is, $x = 2 u$ for an integer $u$ , or $x = 2 u + 1$ for an integer $u$ , and these are the even and odd cases.

givenL1algebra

1.2

In the odd case, $x = 2 u + 1$ gives $x^{2} = 2 (2 u^{2} + 2 u) + 1$ , so $x^{2}$ is odd; the congruence $t^{2} \equiv x^{2} (m o d 2^{3})$ has the solution $t = x$ , so [L2] applied with $a = x^{2}$ and $k = 3$ gives $x^{2} \equiv 1 (m o d 8)$ .

assume-case oddL2F1algebra

1.3

In the even case, $x = 2 u$ gives $x^{2} = 4 u^{2}$ , and by [L1] with $b = 2$ applied to $u$ the integer $u$ is itself either $2 v$ or $2 v + 1$ for an integer $v$ .

assume-case evenL1algebra

2.1

If $u = 2 v$ then $x^{2} = 16 v^{2} = 8 \cdot 2 v^{2}$ , so $8 ∣ x^{2} - 0$ and $x^{2} \equiv 0 (m o d 8)$ .

step 1.3assume-case uevenF1F2algebra

2.2

If $u = 2 v + 1$ then $u^{2} = 2 (2 v^{2} + 2 v) + 1$ , so $x^{2} = 4 u^{2} = 8 (2 v^{2} + 2 v) + 4$ , whence $8 ∣ x^{2} - 4$ and $x^{2} \equiv 4 (m o d 8)$ .

step 1.3assume-case uoddF1F2algebra

3.1

Steps 1.2, 2.1 and 2.2 cover every integer $x$ , so $x^{2}$ is congruent to $0$ , to $1$ or to $4$ modulo $8$ , with $1$ occurring exactly in the odd case.

step 1.2step 2.1step 2.2algebra

4.1

For the modulo- $4$ consequence: in the odd case $8 ∣ x^{2} - 1$ and $4 ∣ 8$ , so [L3] gives $4 ∣ x^{2} - 1$ and $x^{2} \equiv 1 (m o d 4)$ ; in the even case either $8 ∣ x^{2}$ , whence $4 ∣ x^{2}$ by [L3], or $x^{2} = 8 w + 4 = 4 (2 w + 1)$ for an integer $w$ , whence $4 ∣ x^{2}$ directly, so $x^{2} \equiv 0 (m o d 4)$ in both.

step 3.1step 1.2step 2.1step 2.2L3F1F2cases-exhaustive∎

Remarks

Where the odd case comes from. The published criterion Unit square criterion and root count modulo powers of two says that for $k \geq 3$ an odd $a$ is a square modulo $2^{k}$ exactly when $a \equiv 1 (m o d 8)$ . Reading it at $k = 3$ in the direction "soluble implies $a \equiv 1 (m o d 8)$ ", with $a = x^{2}$ and the solution $t = x$ already in hand, is the whole odd case. The elementary route is also short — $x = 2 u + 1$ gives $x^{2} = 4 u (u + 1) + 1$ with $u (u + 1)$ even — and the citation is used instead because the criterion is the general statement of which this is the special case.

Which residues actually occur. All three do: $0 = 0^{2}$ , $1 = 1^{2}$ and $4 = 2^{2}$ realise the residues $0$ , $1$ and $4$ . So the list cannot be shortened, and the modulo- $8$ classification of squares is exactly this list.

Depends on

Used by

Dependency tree · two levels

14 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Evan Dummit, Number Theory (part 9): The Geometry of Numbers, §9.1.3 (standard reference, not scraped)
Karl-Dieter Crisman, Number Theory: In Context and Interactive, §14.2 (standard reference, not scraped)

A square is congruent to 00, 11 or 44 modulo 88