# Residue Class Rings The ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$ consists of representatives for the residue classes of integers modulo $m > 1$. This Section describes the operations in Magma for such rings and their elements. At any stage during a session, Magma will have at most one copy of ${{\mathbb{Z}}/m{\mathbb{Z}}}$ present, for any $m>1$. In other words, different names for the same residue class ring will in fact be different references to the same structure. This saves memory and avoids confusion about different but isomorphic structures. If $m$ is a prime number, the ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$ forms a field; however, Magma has special functions for dealing with finite fields. The operations described here should *not* be used for finite field calculations: the implementation of finite field arithmetic in Magma as described in Chapter [Finite Fields](../FiniteFields/index-finite-fields.md#fldfin) takes full advantage of the special structure of finite fields and leads to superior performance. ## Creation In addition to the general quotient constructor, a number of abbreviations are provided for computing residue class rings. ### `quo: RngInt, RngInt -> RngIntRes` Given the ring of integers ${\mathbb{Z}}$, and an ideal $I$, create the residue class ring modulo the ideal. Note that $Z/I$ does **not** give this residue ring, but rather, in compatibility with ${\mathbb{Z}}$ as a number field order, returns the ideal quotient, namely ${\mathbb{Z}}$ itself (see Section [${\mathbb{Z}}$ as a Number Field Order](number-field-like.md#rngintres-zasnford) above, and the example in Sections [Ideals of ${\mathbb{Z}}$](integer-ideals.md#rngintres-ideal-division)). ### `quo: RngInt, RngIntElt -> RngIntRes` Given the ring of integers ${\mathbb{Z}}$, and an integer $m \ne 0$, create the residue class ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$. ### `ResidueClassRing(m): RngIntElt -> RngIntRes, Map` ### `IntegerRing(m): RngIntElt -> RngIntRes` ### `Integers(m): RngIntElt -> RngIntRes` ### `RingOfIntegers(m): RngIntElt -> RngIntRes` Given an integer greater than zero, create the residue class ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$ and also returns the map from ${\mathbb{Z}}$ into ${{\mathbb{Z}}/m{\mathbb{Z}}}$. ### `ResidueClassField(p): RngIntElt -> FldFin, Map` Given a prime integer $p$ construct the residue class field ${\mathbb{F}}_p$ and the map from ${\mathbb{Z}}$ into ${\mathbb{F}}_p$. ### `ResidueClassRing(Q): RngIntEltFact -> RngIntRes` ### `IntegerRing(Q): RngIntEltFact -> RngIntRes` ### `Integers(Q): RngIntEltFact -> RngIntRes` Create the residue class ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$, where $m$ is the integer corresponding to the factorization sequence $Q$. This is more efficient than creating the ring by $m$ alone, since the factorization $Q$ will be stored so it can be reused later. ### `Example: Residue Ring (ex-d9f52c)` We construct a residue ring having modulus the largest prime not exceeding $2^{16}$. ```magma > p := PreviousPrime(2^16); > p; 65521 > R := ResidueClassRing(p); Residue class ring of integers modulo 65521 ``` Now we try to find an element $x$ in $R$ such that $x^3 = 23$. ```magma > exists(t){x : x in R | x^3 eq 23}; true > t; 12697 ``` ## Coercion As can be seen from the tables in Chapter [Introduction to Rings](../IntroductionToRings/index-introduction-to-rings.md#rngintro), automatic coercion takes place between ${{\mathbb{Z}}/m{\mathbb{Z}}}$ and ${\mathbb{Z}}$ so that a binary operation like $+$ applied to an element of ${{\mathbb{Z}}/m{\mathbb{Z}}}$ and an integer will result in a residue class from ${{\mathbb{Z}}/m{\mathbb{Z}}}$. Using `!`, elements from a prime field ${\bf F}_{p}$ can be coerced into ${{\mathbb{Z}}/p{\mathbb{Z}}}$, and elements from ${{\mathbb{Z}}/p{\mathbb{Z}}}$ can be coerced into ${\bf F}_{p^r}$. Also, transitions between ${{\mathbb{Z}}/m{\mathbb{Z}}}$ and ${{\mathbb{Z}}/n{\mathbb{Z}}}$ can be made using `!` provided that $m$ divides $n$ or $n$ divides $m$. In cases where there is a choice – such as when an element $r$ from ${{\mathbb{Z}}/m{\mathbb{Z}}}$ is coerced into ${{\mathbb{Z}}/n{\mathbb{Z}}}$ with $m$ dividing $n$ – the result will be the residue class containing the representative for $r$. ### `Example: Coercion (ex-155ae3)` ```magma > r := ResidueClassRing(3) ! 5; > r; 2 > ResidueClassRing(6) ! r; 2 ``` So the representative 2 of $5\bmod 3$ is mapped to the residue class $2 \bmod 6$, and not to $5\bmod 6$. ## Elementary Invariants ### `Characteristic(R): RngIntRes -> RngIntResElt` ### `# R: RngIntRes -> RngIntResElt` ### `Modulus(R): RngIntRes -> RngInt` Given a residue class ring $R={{\mathbb{Z}}/m{\mathbb{Z}}}$, this function returns the common modulus $m$ for the elements of $R$. ### `FactoredModulus(R): RngIntRes -> RngIntEltFact` Given a residue class ring $R={{\mathbb{Z}}/m{\mathbb{Z}}}$, this function returns the factorization of the common modulus $m$ for the elements of $R$. ## Structure Operations ### `AdditiveGroup(R): RngIntRes -> GrpAb, Map` Given $R={{\mathbb{Z}}/m{\mathbb{Z}}}$, create the abelian group of integers modulo $m$ under addition. This returns the finite additive abelian group $A$ (of order $m$) together with a map from $A$ to the ring ${{\mathbb{Z}}/m{\mathbb{Z}}}$, sending $A.1$ to $1$. ### `MultiplicativeGroup(R): RngIntRes -> GrpAb, Map` ### `UnitGroup(R): RngIntRes -> GrpAb, Map` Given $R={{\mathbb{Z}}/m{\mathbb{Z}}}$, create the multiplicative group of $R$ as an abelian group. This returns an (additive) abelian group $A$ of order $\phi(m)$, together with a map from $A$ to $R$. ### `sub< R | n >: RngIntRes, RngIntResElt -> RngIntRes` Given $R$, the ring of integers modulo $m$ or an ideal of it, and an element $n$ of $R$ create the ideal of $R$ generated by $n$. ### `Set(R): RngIntRes -> SetEnum` Create the enumerated set consisting of the elements of the residue class ring $R$. ### `Category(R): RngIntRes -> Cat` ### `Parent(R): RngIntRes -> PowerStructure` ### `PrimeRing(R): RngIntRes -> RngIntRes` ### `Center(R): RngIntRes -> RngIntRes` ## Ring Predicates and Booleans ### `IsCommutative(R): RngIntRes -> BoolElt` ### `IsUnitary(R): RngIntRes -> BoolElt` ### `IsFinite(R): RngIntRes -> BoolElt` ### `IsOrdered(R): RngIntRes -> BoolElt` ### `IsField(R): RngIntRes -> BoolElt` ### `IsEuclideanDomain(R): RngIntRes -> BoolElt` ### `IsPID(R): RngIntRes -> BoolElt` ### `IsUFD(R): RngIntRes -> BoolElt` ### `IsDivisionRing(R): RngIntRes -> BoolElt` ### `IsEuclideanRing(R): RngIntRes -> BoolElt` ### `IsPrincipalIdealRing(R): RngIntRes -> BoolElt` ### `IsDomain(R): RngIntRes -> BoolElt` ### `R eq R: RngIntRes, Rng -> BoolElt` ### `R ne R: RngIntRes, Rng -> BoolElt` ## Homomorphisms Ring homomorphisms with domain ${{\mathbb{Z}}/m{\mathbb{Z}}}$ are completely determined by the image of $1$. As usual (see Chapter [Ring of Integers](../Integers/index-integers.md#rngint) ), we require our homomorphisms to map 1 to 1. Therefore, the general homomorphism constructor with domain ${{\mathbb{Z}}/m{\mathbb{Z}}}$ needs no arguments. ### `hom< R -> S | >: RngIntRes, Rng -> Map` Given a residue class ring $R$, and a ring $S$, create a homomorphism from $R$ to $S$, determined by $f(1_R) = 1_S$. Note that it is the responsibility of the user that the map defines a homomorphism!