# 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.

`divrem`

— Method`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.

`mod`

— Method`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.

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

`mod(a_1, b) = mod(a_2, b)`

if and only if $b$ divides $a_1 - a_2$, and`mod(0, b) = 0`

.

`div`

— Method`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.

`mulmod`

— Method`mulmod(f::T, g::T, m::T) where T <: RingElem`

Return `mod(f*g, m)`

but possibly computed more efficiently.

`powermod`

— Method`powermod(f::T, e::Int, m::T) where T <: RingElem`

Return `mod(f^e, m)`

but possibly computed more efficiently.

`invmod`

— Method`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.

`divides`

— Method`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)`

.

`remove`

— Method`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.

`valuation`

— Method`valuation(f::T, p::T) where T <: RingElem`

Return `v`

where $p^v$ is the highest power of $p$ dividing $f$.

See also `remove`

.

`gcd`

— Method`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$.

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.

`gcd`

— Method`gcd(f::T, g::T, hs::T...) where T <: RingElem`

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

.

`gcd`

— Method`gcd(fs::AbstractArray{<:T}) where T <: RingElem`

Return a greatest common divisor of the elements in `fs`

. Requires that `fs`

is not empty.

`lcm`

— Method`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$.

`lcm`

— Method`lcm(f::T, g::T, hs::T...) where T <: RingElem`

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

.

`lcm`

— Method`lcm(fs::AbstractArray{<:T}) where T <: RingElem`

Return a least common multiple of the elements in `fs`

. Requires that `fs`

is not empty.

`gcdx`

— Method`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$.

`gcdinv`

— Method`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}$.

`crt`

— Method`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)`

.

`crt`

— Method`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_lcm`

— Method`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_lcm`

— Method`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$.