LemmaStatement: AI-adaptedProof: AI-adaptedprecheck 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 $Z$

Statement

For every integer $n$ , the relation $a \equiv b (m o d n)$ on $Z$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (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 (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$ ).

[L1]

Divisibility is reflexive and linear: $d ∣ u$ and $d ∣ v$ imply $d ∣ u x + v y$ for all integers $x, y$ ; also $d ∣ u$ implies $d ∣ - u$ (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$ ).

[F2]

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

Proof

technique · direct

1.1F1algebra

Reflexivity: $a - a = 0 = n \cdot 0$ , so $n ∣ (a - a)$ and $a \equiv a (m o d n)$ .

1.2F1L1

Symmetry: if $a \equiv b (m o d n)$ , then $n ∣ (a - b)$ , hence $n ∣ - (a - b) = b - a$ , so $b \equiv a (m o d n)$ .

1.3F1L1algebra

Transitivity: if $a \equiv b (m o d n)$ and $b \equiv c (m o d n)$ , then $n ∣ (a - b)$ and $n ∣ (b - c)$ , hence $n ∣ (a - b) + (b - c) = a - c$ , so $a \equiv c (m o d n)$ .

2.1step 1.1step 1.2step 1.3F2

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

3.1F1algebra∎

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

Depends on

Dependency tree · 2 levels

Sources

K. Conrad, Modular Arithmetic

Congruence modulo every integer is an equivalence relation on ZZ