Alphabeta MathHow 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
- In ℤ/4 the sets A=B={0,2} have | A+B|=2, below the Cauchy–Davenport bound 3 Counterexample
- 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
- A=B={0,1,2} in ℤ/7: the sumset has five elements and the bound is tight Example
- Hom_ℤ(ℤ/m,ℤ/n)≅ℤ/gcd(m,n) for n≥1 Example
- Nonzero constant series can multiply to zero in (ℤ/4ℤ)⟦ x⟧ 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
- The seven lines of the Fano plane meet pairwise in one point, and Fisher's bound is tight Example
- False: [a]ₙ[b]ₙ=[0]ₙ always implies [a]ₙ=[0]ₙ or [b]ₙ=[0]ₙ False statement
- Cyclic shifting is an action of ℤ/m on the words of length m over a set Lemma
- Every finite abelian group is a quotient of (ℤ/n)ᵏ for some n and k Lemma
- For coprime positive m,n, every pair of residue classes modulo m and n has a unique simultaneous class modulo mn Lemma
- For prime q and d≥1, the congruence xᵈ≡1 (mod q) has at most d residue-class solutions 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
- Quadratic residuosity is representative-independent and the residues are the image of squaring Proposition
- Bose's construction gives a Steiner triple system of order 6m+3 for m≥1 Theorem
- Cauchy–Davenport: for p prime and nonempty A,B⊆ℤ/p, | A+B|≥min{p,| A|+| B|-1} Theorem
- 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)≡1 (mod n) Theorem
- Every finite abelian group is the Galois group of some finite Galois extension of ℚ Theorem
- For every n≥1 there are infinitely many primes p with p≡1 (mod 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
- K(μₙ)/K is Galois and σ↦ a_σ embeds its Galois group into (ℤ/n)^× Theorem
- Oddtown: distinct A₁,…,Aₘ⊆[n] with every | Aᵢ| odd and every | Aᵢ∩ Aⱼ| (i≠ j) even satisfy m≤ n Theorem
- Wilson's theorem: for every prime p, (p-1)!≡-1 (mod p) Theorem
Dependency tree · two levels
16 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
- K. Conrad, Modular Arithmetic (standard reference, not scraped)