GitHub

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.

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

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

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

source
AbstractAlgebra.mulmod — Method
mulmod(f::T, g::T, m::T) where T <: RingElem

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

source
Base.powermod — Method
powermod(f::T, e::Int, m::T) where T <: RingElem

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

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

source
AbstractAlgebra.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).

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

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

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

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

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

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

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

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

source
AbstractAlgebra.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}$.

source
AbstractAlgebra.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).

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

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

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

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

source
AbstractAlgebra.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).

source