LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-07-31

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.

Congruence modulo every integer is an equivalence relation on $\mathbb{Z}$

Statement

For every integer $n$ , the relation $a\equiv b\pmod n$ on $\mathbb Z$ (Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(a-b)$ , including the moduli $0$ and $1$ ) is an equivalence relation (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ). For $n=0$ it is equality, and for $n=1$ it is the universal relation.

Facts & Assumptions

Given: An integer $n$ and integers $a,b,c$ .

[F1]

$a\equiv b\pmod n$ means $n\mid(a-b)$ (Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(a-b)$ , including the moduli $0$ and $1$ ).

[L1]

Divisibility is reflexive and linear: $d\mid u$ and $d\mid v$ imply $d\mid ux+vy$ for all integers $x,y$ ; also $d\mid u$ implies $d\mid -u$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[F2]

An equivalence relation is reflexive, symmetric and transitive (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

Proof

technique · direct

1.1

Reflexivity: $a-a=0=n\cdot0$ , so $n\mid(a-a)$ and $a\equiv a\pmod n$ .

F1algebra

1.2

Symmetry: if $a\equiv b\pmod n$ , then $n\mid(a-b)$ , hence $n\mid-(a-b)=b-a$ , so $b\equiv a\pmod n$ .

F1L1

1.3

Transitivity: if $a\equiv b\pmod n$ and $b\equiv c\pmod n$ , then $n\mid(a-b)$ and $n\mid(b-c)$ , hence $n\mid(a-b)+(b-c)=a-c$ , so $a\equiv c\pmod n$ .

F1L1algebra

2.1

Steps 1.1, 1.2 and 1.3 establish the three clauses in [F2], so congruence modulo $n$ is an equivalence relation.

step 1.1step 1.2step 1.3F2

3.1

When $n=0$ , [F1] reads $0\mid(a-b)$ , which is equivalent to $a=b$ ; when $n=1$ , it always holds because $a-b=1\cdot(a-b)$ .

F1algebra∎

Depends on

Used by

The congruence class [a]ₙ and the quotient set ℤ/n Definition

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 37 results over 13 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

K. Conrad, Modular Arithmetic (standard reference, not scraped)

Congruence modulo every integer is an equivalence relation on Z\mathbb{Z}Z