One of the most fundamental datatypes in every programming language is
the integer type. **GAP3** is no exception.

**GAP3** integers are entered as a sequence of digits optionally preceded
by a `+`

sign for positive integers or a `-`

sign for negative integers.
The size of integers in **GAP3** is only limited by the amount of available
memory, so you can compute with integers having thousands of digits.

gap> -1234; -1234 gap> 123456789012345678901234567890123456789012345678901234567890; 123456789012345678901234567890123456789012345678901234567890

The first sections in this chapter describe the operations applicable to integers (see Comparisons of Integers, Operations for Integers, QuoInt and RemInt).

The next sections describe the functions that test whether an object is an integer (see IsInt) and convert objects of various types to integers (see Int).

The next sections describe functions related to the ordering of integers (see AbsInt, SignInt).

The next section describes the function that computes a Chinese remainder (see ChineseRem).

The next sections describe the functions related to the ordering of integers, logarithms, and roots (LogInt, RootInt, SmallestRootInt).

The **GAP3** object `Integers`

is the ring domain of all integers. So all
set theoretic functions are also applicable to this domain (see chapter
Domains and Set Functions for Integers). The only serious use of
this however seems to be the generation of random integers.

Since the integers form a Euclidean ring all the ring functions are applicable to integers (see chapter Rings, Ring Functions for Integers, Primes, IsPrimeInt, IsPrimePowerInt, NextPrimeInt, PrevPrimeInt, FactorsInt, DivisorsInt, Sigma, Tau, and MoebiusMu).

Since the integers are naturally embedded in the field of rationals all the field functions are applicable to integers (see chapter Fields and Field Functions for Rationals).

Many more functions that are mainly related to the prime residue group of integers modulo an integer are described in chapter Number Theory.

The external functions are in the file `LIBNAME/"integer.g"`

.

- Comparisons of Integers
- Operations for Integers
- QuoInt
- RemInt
- IsInt
- Int
- AbsInt
- SignInt
- IsOddInt
- IsEvenInt
- ChineseRem
- LogInt
- RootInt
- SmallestRootInt
- Set Functions for Integers
- Ring Functions for Integers
- Primes
- IsPrimeInt
- IsPrimePowerInt
- NextPrimeInt
- PrevPrimeInt
- FactorsInt
- DivisorsInt
- Sigma
- Tau
- MoebiusMu

`n1` = `n2`

`n1` <> `n2`

The equality operator `=`

evaluates to `true`

if the integer `n1` is
equal to the integer `n2` and `false`

otherwise. The inequality operator
`<>`

evaluates to `true`

if `n1` is not equal to `n2` and `false`

otherwise.

Integers can also be compared to objects of other types; of course, they are never equal.

```
gap> 1 = 1;
true
gap> 1 <> 0;
true
gap> 1 = (1,2); #
````(1,2)`

is a permutation
false

`n1` < `n2`

`n1` <= `n2`

`n1` > `n2`

`n1` >= `n2`

The operators `<`

, `<=`

, `>`

, and `=>`

evaluate to `true`

if the
integer `n1` is less than, less than or equal to, greater than, or
greater than or equal to the integer `n2`, respectively.

Integers can also be compared to objects of other types, they are considered smaller than any other object, except rationals, where the ordering reflects the ordering of the rationals (see Comparisons of Rationals).

gap> 1 < 2; true gap> 1 < -1; false gap> 1 < 3/2; true gap> 1 < false; true

`n1` + `n2`

The operator `+`

evaluates to the sum of the two integers `n1` and `n2`.

`n1` - `n2`

The operator `-`

evaluates to the difference of the two integers `n1` and
`n2`.

`n1` * `n2`

The operator `*`

evaluates to the product of the two integers `n1` and
`n2`.

`n1` / `n2`

The operator `/`

evaluates to the quotient of the two integers `n1` and
`n2`. If the divisor does not divide the dividend the quotient is a
rational (see Rationals). If the divisor is 0 an error is signalled.
The integer part of the quotient can be computed with `QuoInt`

(see
QuoInt).

`n1` mod `n2`

The operator `mod`

evaluates to the smallest positive representative of
the residue class of the left operand modulo the right, i.e.,

is the unique `i` mod
`k``m` in the range `[0 .. AbsInt(`

such that `k`)-1]`k`
divides

. If the right operand is 0 an error is signalled.
The remainder of the division can be computed with `i` - `m``RemInt`

(see
RemInt).

`n1` ^ `n2`

The operator `^`

evaluates to the `n2`-th power of the integer `n1`. If
`n2` is a positive integer then

is `n1`^`n2`

(`n1`* `n1`* ..* `n1``n2` factors). If `n2` is a negative integer

is defined as
`n1`^`n2`*1 / n1^{-n2}*. If 0 is raised to a negative power an error is
signalled. Any integer, even 0, raised to the zeroth power yields 1.

Since integers embed naturally into the field of rationals all the rational operations are available for integers too (see Operations for Rationals).

For the precedence of the operators see Operations.

gap> 2 * 3 + 1; 7

`QuoInt( `

`n1`, `n2` )

`QuoInt`

returns the integer part of the quotient of its integer
operands.

If `n1` and `n2` are positive `QuoInt( `

is the largest
positive integer `n1`, `n2` )`q` such that

. If `q`*`n2` <= `n1``n1` or `n2` or
both are negative the absolute value of the integer part of the quotient
is the quotient of the absolute values of `n1` and `n2`, and the sign of
it is the product of the signs of `n1` and `n2`.

`RemInt`

(see RemInt) can be used to compute the remainder.

gap> QuoInt(5,2); QuoInt(-5,2); QuoInt(5,-2); QuoInt(-5,-2); 2 -2 -2 2

`RemInt( `

`n1`, `n2` )

`RemInt`

returns the remainder of its two integer operands.

If `n2` is not equal to zero `RemInt( `

. Note that the rules given for `n1`, `n2` ) = `n1` - `n2`*
QuoInt( `n1`, `n2` )`QuoInt`

(see
QuoInt) imply that `RemInt( `

has the same sign as `n1`, `n2` )`n1` and
its absolute value is strictly less than the absolute value of `n2`.
Dividing by 0 signals an error.

gap> RemInt(5,2); RemInt(-5,2); RemInt(5,-2); RemInt(-5,-2); 1 -1 1 -1

`IsInt( `

`obj` )

`IsInt`

returns `true`

if `obj`, which can be an arbitrary object, is an
integer and `false`

otherwise. `IsInt`

will signal an error if `obj` is
an unbound variable.

```
gap> IsInt( 1 );
true
gap> IsInt( IsInt );
false #
````IsInt`

is a function, not an integer

`Int( `

`obj` )

`Int`

converts an object `obj` to an integer. If `obj` is an integer
`Int`

will simply return `obj`.

If `obj` is a rational number (see Rationals) `Int`

returns the unique
integer that has the same sign as `obj` and the largest absolute value
not larger than the absolute value of `obj`.

If `obj` is an element of the prime field of a finite field `F`, `Int`

returns the least positive integer `n` such that

(see IntFFE).
`n`* `F`.one = `obj`

If `obj` is not of one of the above types an error is signalled.

gap> Int( 17 ); 17 gap> Int( 17 / 3 ); 5 gap> Int( Z(5^3)^62 ); 4 #Z(5^{3})^{62}=(Z(5^{3})^{124/4})^{2}=Z(5)^{2}=PrimitiveRoot(5)^{2}=2^{2}

`AbsInt( `

`n` )

`AbsInt`

returns the absolute value of the integer `n`, i.e., `n` if `n`
is positive, -`n` if `n` is negative and 0 if `n` is 0 (see SignInt).

gap> AbsInt( 33 ); 33 gap> AbsInt( -214378 ); 214378 gap> AbsInt( 0 ); 0

`SignInt( `

`obj` )

`SignInt`

returns the sign of the integer `obj`, i.e., 1 if `obj` is
positive, -1 if `obj` is negative and 0 if `obj` is 0 (see AbsInt).

gap> SignInt( 33 ); 1 gap> SignInt( -214378 ); -1 gap> SignInt( 0 ); 0

`IsOddInt( `

`i` )

Determines whether `i` is odd.

gap> IsOddInt(3);IsOddInt(4); true false

`IsEvenInt( `

`i` )

Determines whether `i` is even.

gap> IsEvenInt(3);IsEvenInt(4); false true

`ChineseRem( `

`moduli`, `residues` )

`ChineseRem`

returns the combination of the `residues` modulo the
`moduli`, i.e., the unique integer `c` from `[0..Lcm(`

such
that `moduli`)-1]

modulo `c` = `residues`[i]

for all `moduli`[i]`i`, if it
exists. If no such combination exists `ChineseRem`

signals an error.

Such a combination does exist if and only if

mod `residues`[`i`]=`residues`[`k`]`Gcd(`

for every pair `moduli`[`i`],`moduli`[`k`])`i`, `k`. Note that this implies that such a combination
exists if the moduli are pairwise relatively prime. This is called the
Chinese remainder theorem.

gap> ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] ); 53 gap> ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] ); 103 gap> ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] ); Error, the residues must be equal modulo 2

`LogInt( `

`n`, `base` )

`LogInt`

returns the integer part of the logarithm of the positive
integer `n` with respect to the positive integer `base`, i.e., the
largest positive integer `exp` such that *base ^{exp} <= n*.

`LogInt`

will signal an error if either

gap> LogInt( 1030, 2 ); 10 #2gap> LogInt( 1, 10 ); 0^{10}= 1024

`RootInt( `

`n` )

`RootInt( `

`n`, `k` )

`RootInt`

returns the integer part of the `k`th root of the integer `n`.
If the optional integer argument `k` is not given it defaults to 2, i.e.,
`RootInt`

returns the integer part of the square root in this case.

If `n` is positive `RootInt`

returns the largest positive integer *r*
such that *r ^{k} <= n*. If

`RootInt`

returns `-RootInt( -``n`, `k` )

. If `RootInt`

will cause an error. `RootInt`

will also cause an error if

gap> RootInt( 361 ); 19 gap> RootInt( 2 * 10^12 ); 1414213 gap> RootInt( 17000, 5 ); 7 #7^{5}= 16807

`SmallestRootInt( `

`n` )

`SmallestRootInt`

returns the smallest root of the integer `n`.

The smallest root of an integer *n* is the integer *r* of smallest
absolute value for which a positive integer *k* exists such that *n =
r ^{k}*.

gap> SmallestRootInt( 2^30 ); 2 gap> SmallestRootInt( -(2^30) ); -4 # note that(-2)gap> SmallestRootInt( 279936 ); 6 gap> LogInt( 279936, 6 ); 7 gap> SmallestRootInt( 1001 ); 1001^{30}= +(2^{30})

`SmallestRootInt`

can be used to identify and decompose powers of primes
as is demonstrated in the following example (see IsPrimePowerInt)

p := SmallestRootInt( q ); n := LogInt( q, p ); if not IsPrimeInt(p) then Error("GF: <q> must be a primepower"); fi;

As already mentioned in the first section of this chapter, `Integers`

is
the domain of all integers. Thus in principle all set theoretic
functions, for example `Intersection`

, `Size`

, and so on can be applied
to this domain. This seems generally of little use.

gap> Intersection( Integers, [ 0, 1/2, 1, 3/2 ] ); [ 0, 1 ] gap> Size( Integers ); "infinity"

`Random( Integers )`

This seems to be the only useful domain function that can be applied to
the domain `Integers`

. It returns pseudo random integers between -10 and
10 distributed according to a binomial distribution.

gap> Random( Integers ); 1 gap> Random( Integers ); -4

To generate uniformly distributed integers from a range, use the
construct `Random( [ `

.
`low` .. `high` ] )

As was already noted in the introduction to this chapter the integers form a Euclidean ring, so all ring functions (see chapter Rings) are applicable to the integers. This section comments on the implementation of those functions for the integers and tells you how you can call the corresponding functions directly, for example to save time.

`IsPrime( Integers, `

`n` )

This is implemented by `IsPrimeInt`

, which you can call directly to save
a little bit of time (see IsPrimeInt).

`Factors( Integers, `

`n` )

This is implemented as by `FactorsInt`

, which you can call directly to
save a little bit of time (see FactorsInt).

`EuclideanDegree( Integers, `

`n` )

The Euclidean degree of an integer is of course simply the absolute value
of the integer. Calling `AbsInt`

directly will be a little bit faster.

`EuclideanRemainder( Integers, `

`n`, `m` )

This is implemented as `RemInt( `

, which you can use directly
to save a lot of time.
`n`, `m` )

`EuclideanQuotient( Integers, `

`n`, `m` )

This is implemented as `QuoInt( `

, which you can use directly
to save a lot of time.
`n`, `m` )

`QuotientRemainder( Integers, `

`n`, `m` )

This is implemented as `[ QuoInt(`

, which you
can use directly to save a lot of time.
`n`,`m`), RemInt(`n`,`m`) ]

`QuotientMod( Integers, `

`n1`, `n2`, `m` )

This is implemented as `(`

, which you can use
directly to save a lot of time.
`n1` / `n2`) mod `m`

`PowerMod( Integers, `

`n`, `e`, `m` )

This is implemented by `PowerModInt`

, which you can call directly to save
a little bit of time. Note that using

will
generally be slower, because it can not reduce intermediate results like
`n` ^ `e` mod `m``PowerMod`

.

`Gcd( Integers, `

`n1`, `n2`.. )

This is implemented by `GcdInt`

, which you can call directly to save a
lot of time. Note that `GcdInt`

takes only two arguments, not several as
`Gcd`

does.

`Gcdex( `

`n1`, `n2` )

`Gcdex`

returns a record. The component `gcd`

is the gcd of `n1` and
`n2`.

The components `coeff1`

and `coeff2`

are integer cofactors such that

.`g`.gcd = `g`.coeff1*`n1` + `g`.coeff2*`n2`

If `n1` and `n2` both are nonzero, `AbsInt( `

is less than or
equal to `g`.coeff1 )`AbsInt(`

and `n2`) / (2*`g`.gcd)`AbsInt( `

is less
than or equal to `g`.coeff2 )`AbsInt(`

.
`n1`) / (2*`g`.gcd)

The components `coeff3`

and `coeff4`

are integer cofactors such that

`0 = `

.`g`.coeff3*`n1` + `g`.coeff4*`n2`

If `n1` or `n2` or are both nonzero `coeff3`

is `-`

and
`n2` / `g`.gcd`coeff4`

is

.
`n1` / `g`.gcd

The coefficients always form a unimodular matrix, i.e., the determinant

`g`.coeff1*`g`.coeff4 - `g`.coeff3*`g`.coeff2

is 1 or -1.

gap> Gcdex( 123, 66 ); rec( gcd := 3, coeff1 := 7, coeff2 := -13, coeff3 := -22, coeff4 := 41 ) # 3 = 7*123 - 13*66, 0 = -22*123 + 41*66 gap> Gcdex( 0, -3 ); rec( gcd := 3, coeff1 := 0, coeff2 := -1, coeff3 := 1, coeff4 := 0 ) gap> Gcdex( 0, 0 ); rec( gcd := 0, coeff1 := 1, coeff2 := 0, coeff3 := 0, coeff4 := 1 )

`Lcm( Integers, `

`n1`, `n2`.. )

This is implemented as `LcmInt`

, which you can call directly to save a
little bit of time. Note that `LcmInt`

takes only two arguments, not
several as `Lcm`

does.

`Primes[ `

`n` ]

`Primes`

is a set, i.e., a sorted list, of the 168 primes less than 1000.

`Primes`

is used in `IsPrimeInt`

(see IsPrimeInt) and `FactorsInt`

(see
FactorsInt) to cast out small prime divisors quickly.

gap> Primes[1]; 2 gap> Primes[100]; 541

`IsPrimeInt( `

`n` )

`IsPrimeInt`

returns `false`

if it can prove that `n` is composite and
`true`

otherwise. By convention `IsPrimeInt(0) = IsPrimeInt(1) = false`

and we define `IsPrimeInt( -`

.
`n` ) = IsPrimeInt( `n` )

`IsPrimeInt`

will return `true`

for all prime *n*. `IsPrimeInt`

will
return `false`

for all composite *n < 10 ^{13}* and for all composite

`IsPrimeInt`

is a proper primality test. It is conceivable that
`IsPrimeInt`

may return `true`

for some composite `IsPrimeInt`

is a probable-primality test. If composites that fool `IsPrimeInt`

do
exist, they would be extremly rare, and finding one by pure chance is
less likely than finding a bug in
`IsPrimeInt`

is a deterministic algorithm, i.e., the computations involve
no random numbers, and repeated calls will always return the same result.
`IsPrimeInt`

first does trial divisions by the primes less than 1000.
Then it tests that *n* is a strong pseudoprime w.r.t. the base 2.
Finally it tests whether *n* is a Lucas pseudoprime w.r.t. the smallest
quadratic nonresidue of *n*. A better description can be found in the
comment in the library file `integer.g`

.

The time taken by `IsPrimeInt`

is approximately proportional to the third
power of the number of digits of `n`. Testing numbers with several
hundreds digits is quite feasible.

gap> IsPrimeInt( 2^31 - 1 ); true gap> IsPrimeInt( 10^42 + 1 ); false

`IsPrimePowerInt( `

`n` )

`IsPrimePowerInt`

returns `true`

if the integer `n` is a prime power and
`false`

otherwise.

*n* is a **prime power** if there exists a prime *p* and a positive integer
*i* such that *p ^{i} = n*. If

Note that `IsPrimePowerInt`

uses `SmallestRootInt`

(see
SmallestRootInt) and a probable-primality test (see IsPrimeInt).

gap> IsPrimePowerInt( 31^5 ); true gap> IsPrimePowerInt( 2^31-1 ); true #2is actually a prime gap> IsPrimePowerInt( 2^63-1 ); false gap> Filtered( [-10..10], IsPrimePowerInt ); [ -8, -7, -5, -3, -2, 2, 3, 4, 5, 7, 8, 9 ]^{31}-1

`NextPrimeInt( `

`n` )

`NextPrimeInt`

returns the smallest prime which is strictly larger than
the integer `n`.

Note that `NextPrimeInt`

uses a probable-primality test (see
IsPrimeInt).

gap> NextPrimeInt( 541 ); 547 gap> NextPrimeInt( -1 ); 2

`PrevPrimeInt( `

`n` )

`PrevPrimeInt`

returns the largest prime which is strictly smaller than
the integer `n`.

Note that `PrevPrimeInt`

uses a probable-primality test (see
IsPrimeInt).

gap> PrevPrimeInt( 541 ); 523 gap> PrevPrimeInt( 1 ); -2

`FactorsInt( `

`n` )

`FactorsInt`

returns a list of the prime factors of the integer `n`. If
the `i`th power of a prime divides `n` this prime appears `i` times. The
list is sorted, that is the smallest prime factors come first. The first
element has the same sign as `n`, the others are positive. For any
integer `n` it holds that `Product( FactorsInt( `

.
`n` ) ) = `n`

Note that `FactorsInt`

uses a probable-primality test (see IsPrimeInt).
Thus `FactorsInt`

might return a list which contains composite integers.

The time taken by `FactorsInt`

is approximately proportional to the
square root of the second largest prime factor of `n`, which is the last
one that `FactorsInt`

has to find, since the largest factor is simply
what remains when all others have been removed. Thus the time is roughly
bounded by the fourth root of `n`. `FactorsInt`

is guaranteed to find
all factors less than *10 ^{6}* and will find most factors less than

`FactorsInt`

may not be able to factor

gap> FactorsInt( -Factorial(6) ); [ -2, 2, 2, 2, 3, 3, 5 ] gap> Set( FactorsInt( Factorial(13)/11 ) ); [ 2, 3, 5, 7, 13 ] gap> FactorsInt( 2^63 - 1 ); [ 7, 7, 73, 127, 337, 92737, 649657 ] gap> FactorsInt( 10^42 + 1 ); [ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ]

`DivisorsInt( `

`n` )

`DivisorsInt`

returns a list of all positive **divisors** of the integer
`n`. The list is sorted, so it starts with 1 and ends with `n`. We
define `DivisorsInt( -`

. Since the set of
divisors of 0 is infinite calling `n` ) = DivisorsInt( `n` )`DivisorsInt( 0 )`

causes an error.

`DivisorsInt`

calls `FactorsInt`

(see FactorsInt) to obtain the prime
factors. `Sigma`

(see Sigma) computes the sum, `Tau`

(see Tau) the
number of positive divisors.

gap> DivisorsInt( 1 ); [ 1 ] gap> DivisorsInt( 20 ); [ 1, 2, 4, 5, 10, 20 ] gap> DivisorsInt( 541 ); [ 1, 541 ]

`Sigma( `

`n` )

`Sigma`

returns the sum of the positive divisors (see DivisorsInt) of
the integer `n`.

`Sigma`

is a multiplicative arithmetic function, i.e., if *n* and *m* are
relatively prime we have *σ(n m) = σ(n) σ(m)*. Together
with the formula *σ(p ^{e}) = (p^{e+1}-1) / (p-1)* this allows you to
compute

Integers *n* for which *σ(n)=2 n* are called perfect. Even perfect
integers are exactly of the form *2 ^{n-1}(2^{n}-1)* where

`Sigma`

usually spends most of its time factoring `n` (see FactorsInt).

gap> Sigma( 0 ); Error, Sigma: <n> must not be 0 gap> Sigma( 1 ); 1 gap> Sigma( 1009 ); 1010 # thus 1009 is a prime gap> Sigma( 8128 ) = 2*8128; true # thus 8128 is a perfect number

`Tau( `

`n` )

`Tau`

returns the number of the positive divisors (see DivisorsInt) of
the integer `n`.

`Tau`

is a multiplicative arithmetic function, i.e., if *n* and *m* are
relatively prime we have *τ(n m) = τ(n) τ(m)*. Together with
the formula *τ(p ^{e}) = e+1* this allows us to compute

`Tau`

usually spends most of its time factoring `n` (see FactorsInt).

gap> Tau( 0 ); Error, Tau: <n> must not be 0 gap> Tau( 1 ); 1 gap> Tau( 1013 ); 2 # thus 1013 is a prime gap> Tau( 8128 ); 14 gap> Tau( 36 ); 9 #τ(n)is odd if and only ifnis a perfect square

`MoebiusMu( `

`n` )

`MoebiusMu`

computes the value of the **Moebius function** for the integer
`n`. This is 0 for integers which are not squarefree, i.e., which are
divisible by a square *r ^{2}*. Otherwise it is 1 if

The importance of *μ* stems from the so called inversion formula.
Suppose *f(n)* is a function defined on the positive integers and let
*g(n)=∑ _{d | n}f(d)*. Then

`MoebiusMu`

usually spends all of its time factoring `n` (see
FactorsInt).

gap> MoebiusMu( 60 ); 0 gap> MoebiusMu( 61 ); -1 gap> MoebiusMu( 62 ); 1

gap3-jm

11 Mar 2019