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.
For , every class in has one representative with , so ; while is in bijection with
Statement
Let be a positive integer. Every class in (The congruence class and the quotient set ) contains exactly one integer with . Consequently the map
is a bijection from the von Neumann natural to , and . This includes , where the only representative is . For , the map is a bijection .
Facts & Assumptions
Given: A positive integer and integers ; separately, the modulus .
For there are unique integers with and (Division with remainder in : for and there are unique with and ).
exactly when (The congruence class and the quotient set ).
The natural-number embedding into is injective and has image the nonnegative integers; the von Neumann natural is the set of naturals (The naturals embed in the integers, The natural numbers (von Neumann)).
A bijection transports finite cardinality, and (Injection, surjection, bijection, The cardinality of a finite set).
Proof
By [L1], write with . Then , so .
If and , then for some integer , so . Both and express with a remainder in the range from to , so uniqueness in [L1] gives .
At modulus , [F1] says exactly when , exactly when . Hence is injective, and it is surjective by the definition of the quotient set.
Thus from the natural to is surjective by step 1.1 and injective by step 1.2, hence bijective.
Since is finite with cardinality , the bijection in step 2.1 gives . At its domain is , so there is one class.
Steps 1.1 through 3.1 prove the positive-modulus statement, and step 1.3 proves the bijection at modulus .
Depends on
- The congruence class $[a]_n$ and the quotient set $\mathbb{Z}/n$
- Division with remainder in $\mathbb{Z}$: for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$
- The cardinality $\lvert A\rvert$ of a finite set
- Injection, surjection, bijection
- The natural numbers $\mathbb{N}$ (von Neumann)
- The naturals embed in the integers
Used by
- φ(1)=1, and φ(p)=p-1 for every prime p Corollary
- 2ℤ has index 2 in ℤ and is nevertheless equinumerous with ℤ Counterexample
- The action of ℤ/2 on two disjoint two-point orbits is free but not transitive Counterexample
- ℤ/1 has one element and satisfies [0]₁=[1]₁, so it is not a field Counterexample
- The unit group (ℤ/n)^× and Euler's totient φ(n)=|(ℤ/n)^×| for n≥1 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∣ a², b², aba⁻¹b⁻¹⟩≅(ℤ/2)×(ℤ/2) Example
- ⟨ a∣ aⁿ⟩≅(ℤ/n,+) for every n≥ 1 Example
- A modulus n>1 is composite exactly when two nonzero classes in ℤ/n have product [0]ₙ Example
- An involution on five points has three fixed points and one two-point orbit, verifying 5≡3pmod2 Example
- Dₙ≅⟨ r,s∣ rⁿ, s², srs⁻¹r⟩ for the dihedral group Dₙ=⟨{ρ,σ}⟩leqSym(ℤ/n), n≥ 3 Example
- For n≥1, the cosets of nℤ are the n congruence classes modulo n Example
- The action of ℤ/6 on the cosets of {0,3} is transitive with kernel {0,3} and is not faithful Example
- The Chinese remainder bijection ℤ/12→ℤ/3×ℤ/4 computed on all standard representatives Example
- The four cosets of 4ℤ in (ℤ,+) reproduce addition modulo 4 Example
- The four rotations of a square act freely, transitively and faithfully on its vertices Example
- There are six binary necklaces of length four up to rotation Example
- For a prime p and k≥1, multiplication by p bijects the standard representatives modulo pᵏ⁻¹ with the representatives modulo pᵏ divisible by p Lemma
- In (ℤ/p)^×, inversion pairs every class except [1]ₚ and [-1]ₚ, which are the only self-inverse classes Lemma
- Cauchy's theorem: if a prime p divides |G|, then G has an element of order p Theorem
- Euler's product formula φ(n)=n∏_p∣ n(1-1/p)=∏_pᵏ∥ n(pᵏ-pᵏ⁻¹) for n≥1, stated through a finite injective list of its prime divisors Theorem
- For a prime p and k≥1, φ(pᵏ)=pᵏ-pᵏ⁻¹ Theorem
- For every positive integer n, ∑_d∣ n, d>0φ(d)=n Theorem
- For n≥1, ax≡ bpmod n is solvable exactly when gcd(a,n)∣ b, and then has exactly gcd(a,n) solution classes modulo n 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: 68 results over 19 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)