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 ff by gg. A DivideError should be thrown if gg is zero.

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

Return the Euclidean remainder of ff by gg. A DivideError should be thrown if gg 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 bb divides a1a2a_1 - a_2, and
  2. mod(0, b) = 0.
source
divMethod
div(f::T, g::T) where T <: RingElem

Return the Euclidean quotient of ff by gg. A DivideError should be thrown if gg is zero.

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

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

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

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

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

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

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

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

Return a pair, flag, q, where flag is set to true if gg divides ff, in which case q is set to the quotient, or flag is set to false and q is undefined.

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

Check if x is divisible by y, i.e. if x=zyx = zy for some zz.

source
is_associatedMethod
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.

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

Return a pair v, q where pvp^v is the highest power of pp dividing ff and qq is the cofactor after ff is divided by this power.

See also valuation, which only returns the valuation.

source
valuationMethod
valuation(f::T, p::T) where T <: RingElem

Return v where pvp^v is the highest power of pp dividing ff.

See also remove.

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

Return a greatest common divisor of aa and bb, i.e., an element gg which is a common divisor of aa and bb, and with the property that any other common divisor of aa and bb divides gg.

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.

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

Return a greatest common divisor of ff, gg and the elements in hs.

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

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

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

Return a least common multiple of ff and gg, i.e., an element dd which is a common multiple of ff and gg, and with the property that any other common multiple of ff and gg is a multiple of dd.

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

Return a least common multiple of ff, gg and the elements in hs.

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

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

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

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

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

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

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

Return an element congruent to r1r_1 modulo m1m_1 and r2r_2 modulo m2m_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).

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

Return an element congruent to rir_i modulo mim_i for each ii.

source
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 r1r_1 modulo m1m_1 and r2r_2 modulo m2m_2 and the least common multiple of m1m_1 and m2m_2. If check = true and no solution exists, an error is thrown.

source
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 rir_i modulo mim_i for each ii and the least common multiple of the mim_i.

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

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

source
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 AA, i.e. the returned array generated multiplicatively the same ideals as the input and are pairwise coprime.

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

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

source