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$, andmod(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$.
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).