The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$

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

• Extended-Euclidean modular inverse with bounded bit cost Algorithm
• Reversible modular multiplication by a unit Algorithm
• Shor factoring with verified output and bounded outer retries Algorithm
• Compact and discrete transforms are the two extreme Plancherel cases Corollary
• The oriented intersection number reduces to the mod 2 number Corollary
• A coproduct-preserving left exact module functor is not tensor Counterexample
• Both finite supports cannot be singletons when N>1 Counterexample
• Cyclic convolution wraps a high coefficient without zero padding Counterexample
• 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
• The radix-two split fails for odd N Counterexample
• The short exact sequence to Sₙ does not prove Bₙ torsion-free Counterexample
• Visible Artin relations alone do not prove presentation completeness Counterexample
• Addition and multiplication on ℤ/n by [a]ₙ+[b]ₙ=[a+b]ₙ and [a]ₙ[b]ₙ=[ab]ₙ Definition
• Binary dot product as parity Definition
• Binary residue carrier and operations Definition
• Morse homology of a Morse--Smale pair Definition
• The continuation chain map Definition
• The counting inner product on ℂ^ℤ/Nℤ Definition
• The mod 2 intersection number Definition
• The mod-two degree of a map to a sphere Definition
• The mod-two Morse chain group Definition
• The mod-two Morse differential Definition
• The principal congruence subgroup Gamma(2) Definition
• The recursive radix-two fast Fourier transform Definition
• The unitary discrete Fourier transform on ℤ/Nℤ Definition
• The unnormalised cyclic convolution on ℤ/Nℤ Definition
• The unnormalised engineering DFT and its conversion to the unitary transform 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 Shor order sample for factoring fifteen Example
• A=B={0,1,2} in ℤ/7: the sumset has five elements and the bound is tight Example
• Cyclic convolution on ℤ/4ℤ via the DFT Example
• Delta and constant functions are finite DFT extremisers 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
• Shor factoring preprocessing and retry branches Example
• The five characters of Z/5Z and their orthogonality Example
• The four cosets of 4ℤ in (ℤ,+) reproduce addition modulo 4 Example

…and 44 more results.

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)