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.

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

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

is_divisible_by — Method

is_divisible_by(x::T, y::T) where T <: RingElem

Check if x is divisible by y, i.e. if $x = zy$ for some $z$.

is_associated — Method

is_associated(x::T, y::T) where T <: RingElem

Check if x and y are associated, i.e. if x is a unit times y.

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

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.

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

coprime_base — Function

coprime_base(S::Vector{RingElement}) -> Vector{RingElement}

Returns a coprime base for $S$, i.e. the resulting array contains pairwise coprime objects that multiplicatively generate the same set as the input array.

coprime_base(A::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}
coprime_base(A::Vector{AbsSimpleNumFieldOrderElem}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}

A coprime base for the (principal) ideals in $A$, i.e. the returned array generated multiplicatively the same ideals as the input and are pairwise coprime.

coprime_base_push! — Function

coprime_base_push!(S::Vector{RingElem}, a::RingElem) -> Vector{RingElem}

Given an array $S$ of coprime elements, insert a new element, that is, find a coprime base for push(S, a).