# Euclidean Ring Interface

If a ring provides a meaningful Euclidean structure such that a useful Euclidean remainder can be computed practically, various additional functionality is provided by AbstractAlgebra.jl for those rings. This functionality depends on the following functions existing. An implementation must provide divrem, and the remaining are optional as generic fallbacks exist.

divremMethod
divrem(f::T, g::T) where T <: RingElem

Return a pair q, r consisting of the Euclidean quotient and remainder of $f$ by $g$. A DivideError should be thrown if $g$ is zero.

modMethod
mod(f::T, g::T) where T <: RingElem

Return the Euclidean remainder of $f$ by $g$. A DivideError should be thrown if $g$ is zero.

Note

For best compatibility with the internal assumptions made by AbstractAlgebra, the Euclidean remainder function should provide unique representatives for the residue classes; the mod function should satisfy

1. mod(a_1, b) = mod(a_2, b) if and only if $b$ divides $a_1 - a_2$, and
2. mod(0, b) = 0.
divMethod
div(f::T, g::T) where T <: RingElem

Return the Euclidean quotient of $f$ by $g$. A DivideError should be thrown if $g$ is zero.

mulmodMethod
mulmod(f::T, g::T, m::T) where T <: RingElem

Return mod(f*g, m) but possibly computed more efficiently.

powermodMethod
powermod(f::T, e::Int, m::T) where T <: RingElem

Return mod(f^e, m) but possibly computed more efficiently.

invmodMethod
invmod(f::T, m::T) where T <: RingElem

Return an inverse of $f$ modulo $m$, meaning that isone(mod(invmod(f,m)*f,m)) returns true.

If such an inverse doesn't exist, a NotInvertibleError should be thrown.

dividesMethod
divides(f::T, g::T) where T <: RingElem

Return a pair, flag, q, where flag is set to true if $g$ divides $f$, in which case q is set to the quotient, or flag is set to false and q is set to zero(f).

removeMethod
remove(f::T, p::T) where T <: RingElem

Return a pair v, q where $p^v$ is the highest power of $p$ dividing $f$ and $q$ is the cofactor after $f$ is divided by this power.

See also valuation, which only returns the valuation.

gcdMethod
gcd(a::T, b::T) where T <: RingElem

Return a greatest common divisor of $a$ and $b$, i.e., an element $g$ which is a common divisor of $a$ and $b$, and with the property that any other common divisor of $a$ and $b$ divides $g$.

Note

For best compatibility with the internal assumptions made by AbstractAlgebra, the return is expected to be unit-normalized in such a way that if the return is a unit, that unit should be one.

gcdMethod
gcd(f::T, g::T, hs::T...) where T <: RingElem

Return a greatest common divisor of $f$, $g$ and the elements in hs.

gcdMethod
gcd(fs::AbstractArray{<:T}) where T <: RingElem

Return a greatest common divisor of the elements in fs. Requires that fs is not empty.

lcmMethod
lcm(f::T, g::T) where T <: RingElem

Return a least common multiple of $f$ and $g$, i.e., an element $d$ which is a common multiple of $f$ and $g$, and with the property that any other common multiple of $f$ and $g$ is a multiple of $d$.

lcmMethod
lcm(f::T, g::T, hs::T...) where T <: RingElem

Return a least common multiple of $f$, $g$ and the elements in hs.

lcmMethod
lcm(fs::AbstractArray{<:T}) where T <: RingElem

Return a least common multiple of the elements in fs. Requires that fs is not empty.

gcdxMethod
gcdx(f::T, g::T) where T <: RingElem

Return a triple d, s, t such that $d = gcd(f, g)$ and $d = sf + tg$, with $s$ loosely reduced modulo $g/d$ and $t$ loosely reduced modulo $f/d$.

gcdinvMethod
gcdinv(f::T, g::T) where T <: RingElem

Return a tuple d, s such that $d = gcd(f, g)$ and $s = (f/d)^{-1} \pmod{g/d}$. Note that $d = 1$ iff $f$ is invertible modulo $g$, in which case $s = f^{-1} \pmod{g}$.

crtMethod
crt(r1::T, m1::T, r2::T, m2::T; check::Bool=true) where T <: RingElement

Return an element congruent to $r_1$ modulo $m_1$ and $r_2$ modulo $m_2$. If check = true and no solution exists, an error is thrown.

If T is a fixed precision integer type (like Int), the result will be correct if abs(ri) <= abs(mi) and abs(m1 * m2) < typemax(T).

crtMethod
crt(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement

Return an element congruent to $r_i$ modulo $m_i$ for each $i$.

crt_with_lcmMethod
crt_with_lcm(r1::T, m1::T, r2::T, m2::T; check::Bool=true) where T <: RingElement

Return a tuple consisting of an element congruent to $r_1$ modulo $m_1$ and $r_2$ modulo $m_2$ and the least common multiple of $m_1$ and $m_2$. If check = true and no solution exists, an error is thrown.

crt_with_lcmMethod
crt_with_lcm(r::Vector{T}, m::Vector{T}; check::Bool=true) where T <: RingElement

Return a tuple consisting of an element congruent to $r_i$ modulo $m_i$ for each $i$ and the least common multiple of the $m_i$.