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.
mod(f::MyElem, g::MyElem)Returns the Euclidean remainder of $f$ by $g$. A DivideError() should be thrown if $g$ is zero. An error should be thrown if an impossible inverse is encountered.
divrem(f::MyElem, g::MyElem)Returns a pair q, r consisting of the Euclidean quotient and remainder of $f$ by $g$. A DivideError should be thrown if $g$ is zero. An error should be thrown if an impossible inverse is encountered.
div(f::MyElem, g::MyElem)Returns the Euclidean quotient of $f$ by $g$. A DivideError should be thrown if $g$ is zero. An error should be thrown if an impossible inverse is encountered.
mulmod(f::MyElem, g::MyElem, m::MyElem)Returns $fg \pmod{m}$.
powmod(f::MyElem, e::Int, m::MyElem)Returns $f^e \pmod{m}$.
invmod(f::MyElem, m::MyElem)Returns the inverse of $f$ modulo $m$. If such an inverse doesn't exist, an impossible inverse error should be thrown.
divides(f::MyElem, g::MyElem)Returns a pair, flag, q, where flag is set to true if $g$ divides $f$, in which case the quotient is set to the quotient, or flag is set to false and the quotient is set to zero in the same ring as $f$ and $g$.
remove(f::MyElem, p::MyElem)Returns 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.
valuation(f::MyElem, p::MyElem)Returns v where $p^v$ is the highest power of $p$ dividing $f$.
gcd(f::MyElem, g::MyElem)Returns a greatest common divisor of $f$ and $g$.
lcm(f::MyElem, g::MyElem)Returns $fg/gcd(f, g)$ if either $f$ or $g$ is not zero, otherwise it throws a DivideError().
gcdx(f::MyElem, g::MyElem)Returns a triple d, s, t such that $d = gcd(f, g)$ and $d = sf + tg$, with $s$ reduced modulo $g$ and $t$ reduced modulo $f$.
gcdinv(f::MyElem, g::MyElem)Returns 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}$.