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.
The congruence class and the quotient set
Definition
Fix an integer . Congruence modulo is an equivalence relation on by Congruence modulo every integer is an equivalence relation on . The congruence class of modulo is
and the integers modulo form the quotient set
This is the quotient-set construction of Equivalence relation, equivalence class, and the quotient set . By The equivalence classes of an equivalence relation are nonempty, cover , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation, two classes are equal exactly when their representatives are congruent:
At each class is a singleton because congruence modulo is equality. At there is one class, namely itself.
Remarks
- The notation in this item denotes a quotient set. It does not yet assert any algebraic structure.
- Since congruence modulo and modulo are the same relation, their quotient sets are literally the same collection of subsets of .
Depends on
- Congruence modulo every integer is an equivalence relation on $\mathbb{Z}$
- Equivalence relation, equivalence class, and the quotient set $A/{\sim}$
- The equivalence classes of an equivalence relation are nonempty, cover $A$, and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation
Used by
- Over F₂, the equation x+y=0 has exactly two solutions, so the infinite-field hypothesis is necessary Counterexample
- Addition and multiplication on ℤ/n by [a]ₙ+[b]ₙ=[a+b]ₙ and [a]ₙ[b]ₙ=[ab]ₙ Definition
- (ℤ/12)^×={[1],[5],[7],[11]} and φ(12)=4 Example
- (ℤ/8)^×={[1],[3],[5],[7]} is not cyclic because every element squares to [1] Example
- Row operations track determinant correctly for a singular triangular matrix over ℤ/6 Example
- The four cosets of 4ℤ in (ℤ,+) reproduce addition modulo 4 Example
- False: [a]ₙ[b]ₙ=[0]ₙ always implies [a]ₙ=[0]ₙ or [b]ₙ=[0]ₙ False statement
- For coprime positive m,n, every pair of residue classes modulo m and n has a unique simultaneous class modulo mn Lemma
- In (ℤ/p)^×, inversion pairs every class except [1]ₚ and [-1]ₚ, which are the only self-inverse classes Lemma
- For every n∈ℕ, the congruence-class group (ℤ/n,+) is the quotient group (ℤ,+)/nℤ Proposition
- Cauchy's theorem: if a prime p divides |G|, then G has an element of order p Theorem
- Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication Theorem
- Euler's theorem: if n≥1 and gcd(a,n)=1, then a^φ(n)≡1pmod n Theorem
- For every prime p, the two operations on ℤ/p make it a field Theorem
- For n≥ 1, every class in ℤ/n has one representative r with 0≤ r<n, so |ℤ/n|=n; while ℤ/0 is in bijection with ℤ Theorem
- Wilson's theorem: for every prime p, (p-1)!≡-1pmod p Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 32 results over 12 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)