Integer ring
AbstractAlgebra.jl provides a module, implemented in src/julia/Integer.jl
for making Julia BigInt
s conform to the AbstractAlgebra.jl Ring interface.
In addition to providing a parent object ZZ
for Julia BigInt
s, we implement any additional functionality required by AbstractAlgebra.jl.
Because BigInt
cannot be directly included in the AbstractAlgebra.jl abstract type hierarchy, we achieve integration of Julia BigInt
s by introducing a type union, called RingElement
, which is a union of RingElem
and a number of Julia types, including BigInt
. Everywhere that RingElem
is notionally used in AbstractAlgebra.jl, we are in fact using RingElement
, with additional care being taken to avoid ambiguities.
The details of how this is done are technical, and we refer the reader to the implementation for details. For most intents and purposes, one can think of the Julia BigInt
type as belonging to RingElem
.
One other technicality is that Julia defines certain functions for BigInt
, such as sqrt
and exp
differently to what AbstractAlgebra.jl requires. To get around this, we redefine these functions internally to AbstractAlgebra.jl, without redefining them for users of AbstractAlgebra.jl. This allows the internals of AbstractAlgebra.jl to function correctly, without broadcasting pirate definitions of already defined Julia functions to the world.
To access the internal definitions, one can use AbstractAlgebra.sqrt
and AbstractAlgebra.exp
, etc.
Types and parent objects
Integers have type BigInt
, as in Julia itself. We simply supplement the functionality for this type as required for computer algebra.
The parent objects of such integers has type Integers{BigInt}
.
For convenience, we also make Int
a part of the AbstractAlgebra.jl type hierarchy and its parent object (accessible as zz
) has type Integers{Int}
. But we caution that this type is not particularly useful as a model of the integers and may not function as expected within AbstractAlgebra.jl.
Integer constructors
In order to construct integers in AbstractAlgebra.jl, one can first construct the integer ring itself. This is accomplished using the following constructor.
Integers{BigInt}()
This gives the unique object of type Integers{BigInt}
representing the ring of integers in AbstractAlgebra.jl.
In practice, one simply uses ZZ
which is assigned to be the return value of the above constructor. There is no need to call the constructor in practice.
Here are some examples of creating the integer ring and making use of the resulting parent object to coerce various elements into the ring.
Examples
julia> f = ZZ()
0
julia> g = ZZ(123)
123
julia> h = ZZ(BigInt(1234))
1234
Basic ring functionality
The integer ring in AbstractAlgebra.jl implements the full Ring interface and the Euclidean Ring interface.
We give some examples of such functionality.
Examples
julia> f = ZZ(12)
12
julia> h = zero(ZZ)
0
julia> k = one(ZZ)
1
julia> isone(k)
true
julia> iszero(f)
false
julia> T = parent(f)
Integers
julia> f == deepcopy(f)
true
julia> g = f + 12
24
julia> h = powermod(f, 12, ZZ(17))
4
julia> flag, q = divides(f, ZZ(3))
(true, 4)
Integer functionality provided by AbstractAlgebra.jl
The functionality below supplements that provided by Julia itself for its BigInt
type.
Basic functionality
Examples
julia> r = ZZ(-1)
-1
julia> is_unit(r)
true
Divisibility testing
AbstractAlgebra.is_divisible_by
— Methodis_divisible_by(a::Integer, b::Integer)
Return true
if $a$ is divisible by $b$, i.e. if there exists $c$ such that $a = bc$.
AbstractAlgebra.is_associated
— Methodis_associated(a::Integer, b::Integer)
Return true
if $a$ and $b$ are associated, i.e. if there exists a unit $c$ such that $a = bc$. For integers, this reduces to checking if $a$ and $b$ differ by a factor of $1$ or $-1$.
Examples
julia> r = ZZ(6)
6
julia> s = ZZ(3)
3
julia> is_divisible_by(r, s)
true
Square root
AbstractAlgebra.sqrt
— Methodsqrt(a::T; check::Bool=true) where T <: Integer
Return the square root of $a$. By default the function will throw an exception if the input is not square. If check=false
this test is omitted.
AbstractAlgebra.is_square
— Methodis_square(f::PolyRingElem{T}) where T <: RingElement
Return true
if $f$ is a perfect square.
is_square(a::ResFieldElem{T}) where T <: Integer
Return true
if $a$ is a square.
is_square(a::T) where T <: Integer
Return true if $a$ is a square.
AbstractAlgebra.is_square_with_sqrt
— Methodis_square_with_sqrt(a::T) where T <: Integer
Return (true, s)
if $a$ is a perfect square, where $s^2 = a$. Otherwise return (false, 0)
.
AbstractAlgebra.root
— Methodroot(a::T, n::Int; check::Bool=true) where T <: Integer
Return the $n$-th root of $a$. If check=true
the function will test if the input was a perfect $n$-th power, otherwise an exception will be raised. We require $n > 0$.
AbstractAlgebra.iroot
— Methodiroot(a::T, n::Int) where T <: Integer
Return the truncated integer part of the $n$-th root of $a$ (round towards zero). We require $n > 0$ and also $a \geq 0$ if $n$ is even.
AbstractAlgebra.is_power
— Methodis_power(a::T, n::Int) where T <: Integer
Return true, q
if $a$ is a perfect $n$-th power with $a = q^n$. Otherwise return false, 0
. We require $n > 0$.
AbstractAlgebra.exp
— Methodexp(a::T) where T <: Integer
Return $1$ if $a = 0$, otherwise throw an exception. This function is not generally of use to the user, but is used internally in AbstractAlgebra.jl.
exp(a::Rational{T}) where T <: Integer
Return $1$ if $a = 0$, otherwise throw an exception.
Examples
julia> d = AbstractAlgebra.sqrt(ZZ(36))
6
julia> is_square(ZZ(9))
true
julia> m = AbstractAlgebra.exp(ZZ(0))
1
Coprime bases
AbstractAlgebra.ppio
— Methodppio(a::T, b::T)
Return a pair $(c,d)$ such that $a=c*d$ and $c = gcd(a, b^\infty)$ if $a\neq 0$, and $c=b$, $d=0$ if $a=0$.
Examples
julia> c, n = ppio(ZZ(12), ZZ(26))
(4, 3)