# Generic residue rings

AbstractAlgebra.jl provides modules, implemented in `src/Residue.jl`

and `src/residue_field`

for residue rings and fields, respectively, over any Euclidean domain (in practice most of the functionality is provided for GCD domains that provide a meaningful GCD function) belonging to the AbstractAlgebra.jl abstract type hierarchy.

## Generic residue types

AbstractAlgebra.jl implements generic residue rings with type `Generic.ResidueRingElem{T}`

or in the case of residue rings that are known to be fields, `Generic.ResidueFieldElem{T}`

, where `T`

is the type of elements of the base ring. See the file `src/generic/GenericTypes.jl`

for details.

Parent objects of generic residue ring elements have type `Generic.ResidueRing{T}`

and those of residue fields have type `GenericResField{T}`

.

The defining modulus of the residue ring is stored in the parent object.

## Abstract types

All residue element types belong to the abstract type `ResElem{T}`

or `ResFieldElem{T}`

in the case of residue fields, and the residue ring types belong to the abstract type `ResidueRing{T}`

or `ResidueField{T}`

respectively. This enables one to write generic functions that can accept any AbstractAlgebra residue type.

Note that both the generic residue ring type `Generic.ResidueRing{T}`

and the abstract type it belongs to, `ResidueRing{T}`

are both called `ResidueRing`

, and similarly for the residue field types. In each case, the former is a (parameterised) concrete type for a residue ring over a given base ring whose elements have type `T`

. The latter is an abstract type representing all residue ring types in AbstractAlgebra.jl, whether generic or very specialised (e.g. supplied by a C library).

## Residue ring constructors

In order to construct residues in AbstractAlgebra.jl, one must first construct the residue ring itself. This is accomplished with one of the following constructors.

`residue_ring(R::Ring, m::RingElem; cached::Bool = true)`

`residue_field(R::Ring, m::RingElem; cached::Bool = true)`

Given a base ring `R`

and residue $m$ contained in this ring, return the parent object of the residue ring $R/(m)$. By default the parent object `S`

will depend only on `R`

and `m`

and will be cached. Setting the optional argument `cached`

to `false`

will prevent the parent object `S`

from being cached.

The `residue_field`

constructor does the same thing as the `residue_ring`

constructor, but the resulting object has type belonging to `Field`

rather than `Ring`

, so it can be used anywhere a field is expected in AbstractAlgebra.jl. No check is made for maximality of the ideal generated by $m$.

There are also the following for constructing residue rings and fields.

`AbstractAlgebra.quo`

— Method`quo(R::Ring, a::RingElement; cached::Bool = true)`

Returns `S, f`

where `S = residue_ring(R, a)`

and `f`

is the projection map from `R`

to `S`

. This map is supplied as a map with section where the section is the lift of an element of the residue field back to the ring `R`

.

`AbstractAlgebra.quo`

— Method`quo(::Type{Field}, R::Ring, a::RingElement; cached::Bool = true)`

Returns `S, f`

where `S = residue_field(R, a)`

and `f`

is the projection map from `R`

to `S`

. This map is supplied as a map with section where the section is the lift of an element of the residue field back to the ring `R`

.

Here are some examples of creating residue rings and making use of the resulting parent objects to coerce various elements into the residue ring.

**Examples**

```
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1
julia> f = S()
0
julia> g = S(123)
123
julia> h = S(BigInt(1234))
1234
julia> k = S(x + 1)
x + 1
julia> U, f = quo(R, x^3 + 3x + 1)
(Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1, Map: univariate polynomial ring -> residue ring)
julia> U === S
true
```

All of the examples here are generic residue rings, but specialised implementations of residue rings provided by external modules will also usually provide a `residue_ring`

constructor to allow creation of their residue rings.

## Residue constructors

One can use the parent objects of a residue ring to construct residues, as per any ring.

```
(R::ResidueRing)() # constructs zero
(R::ResidueRing)(c::Integer)
(R::ResidueRing)(c::elem_type(R))
(R::ResidueRing{T})(a::T) where T <: RingElement
```

## Functions for types and parents of residue rings

```
base_ring(R::ResidueRing)
base_ring(a::ResElem)
```

Return the base ring over which the ring was constructed.

`parent(a::ResElem)`

Return the parent of the given residue.

`characteristic(R::ResidueRing)`

Return the characteristic of the given residue ring. If the characteristic is not known, an exception is raised.

## Residue ring functions

### Basic functionality

Residue rings implement the Ring interface.

```
zero(R::NCRing)
one(R::NCRing)
iszero(a::NCRingElement)
isone(a::NCRingElement)
```

```
divexact(a::T, b::T) where T <: RingElement
inv(a::T)
```

The Residue Ring interface is also implemented.

`modulus(S::ResidueRing)`

```
data(f::ResElem)
lift(f::ResElem)
```

Return a lift of the residue to the base ring.

The following functions are also provided for residues.

`AbstractAlgebra.modulus`

— Method`modulus(R::ResElem)`

Return the modulus $a$ of the residue ring $S = R/(a)$ that the supplied residue $r$ belongs to.

**Examples**

```
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1
julia> f = S(x + 1)
x + 1
julia> h = zero(S)
0
julia> k = one(S)
1
julia> isone(k)
true
julia> iszero(f)
false
julia> is_unit(f)
true
julia> m = modulus(S)
x^3 + 3*x + 1
julia> d = data(f)
x + 1
julia> U = base_ring(S)
Univariate polynomial ring in x over rationals
julia> V = base_ring(f)
Univariate polynomial ring in x over rationals
julia> T = parent(f)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1
julia> f == deepcopy(f)
true
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
```

### Inversion

`Base.inv`

— Method`Base.inv(a::ResElem)`

Return the inverse of the element $a$ in the residue ring. If an impossible inverse is encountered, an exception is raised.

**Examples**

```
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1
julia> f = S(x + 1)
x + 1
julia> g = inv(f)
1//3*x^2 - 1//3*x + 4//3
```

### Greatest common divisor

`Base.gcd`

— Method`gcd(a::ResElem{T}, b::ResElem{T}) where {T <: RingElement}`

Return a greatest common divisor of $a$ and $b$ if one exists. This is done by taking the greatest common divisor of the data associated with the supplied residues and taking its greatest common divisor with the modulus.

**Examples**

```
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> S = residue_ring(R, x^3 + 3x + 1)
Residue ring of univariate polynomial ring modulo x^3 + 3*x + 1
julia> f = S(x + 1)
x + 1
julia> g = S(x^2 + 2x + 1)
x^2 + 2*x + 1
julia> h = gcd(f, g)
1
```

### Square Root

`AbstractAlgebra.is_square`

— Method`is_square(a::ResFieldElem{T}) where T <: Integer`

Return `true`

if $a$ is a square.

`Base.sqrt`

— Method`sqrt(a::ResFieldElem{T}; check::Bool=true) where T <: Integer`

Return the square root of $a$. By default the function will throw an exception if the input is not square. If `check=false`

this test is omitted.

**Examples**

```
julia> R = residue_field(ZZ, 733)
Residue field of Integers modulo 733
julia> a = R(86)
86
julia> is_square(a)
true
julia> sqrt(a)
532
```

### Random generation

Random residues can be generated using `rand`

. The parameters after the residue ring are used to generate elements of the base ring.

`rand(R::ResidueRing, v...)`

**Examples**

```
julia> R = residue_ring(ZZ, 7)
Residue ring of integers modulo 7
julia> f = rand(R, 0:6)
4
julia> S, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> U = residue_field(S, x^3 + 3x + 1)
Residue field of univariate polynomial ring modulo x^3 + 3*x + 1
julia> g = rand(S, 2:2, -10:10)
-1//4*x^2 - 2//7*x + 1
```