chap14.txt

  
  14 Integers
  
  One  of  the most fundamental datatypes in every programming language is the
  integer type. GAP is no exception.
  
  GAP integers are entered as a sequence of decimal digits optionally preceded
  by  a  +  sign  for positive integers or a - sign for negative integers. The
  size  of  integers in GAP is only limited by the amount of available memory,
  so you can compute with integers having thousands of digits.
  
    Example  
    gap> -1234;
    -1234
    gap> 123456789012345678901234567890123456789012345678901234567890;
    123456789012345678901234567890123456789012345678901234567890
  
  
  Many  more  functions  that are mainly related to the prime residue group of
  integers  modulo  an  integer  are  described  in  chapter 15, and functions
  dealing with combinatorics can be found in chapter 16.
  
  
  14.1 Integers: Global Variables
  
  14.1-1 Integers
  
  Integers global variable
  PositiveIntegers global variable
  NonnegativeIntegers global variable
  
  These  global  variables represent the ring of integers and the semirings of
  positive and nonnegative integers, respectively.
  
    Example  
    gap> Size( Integers ); 2 in Integers;
    infinity
    true
  
  
  Integers is a subset of Rationals (17.1-1), which is a subset of Cyclotomics
  (18.1-2).  See  Chapter 18  for  arithmetic  operations  and  comparison  of
  integers.
  
  14.1-2 IsIntegers
  
  IsIntegers( obj )  Category
  IsPositiveIntegers( obj )  Category
  IsNonnegativeIntegers( obj )  Category
  
  are   the   defining   categories   for   the   domains  Integers  (14.1-1),
  PositiveIntegers (14.1-1), and NonnegativeIntegers (14.1-1).
  
    Example  
    gap> IsIntegers( Integers );  IsIntegers( Rationals );  IsIntegers( 7 );
    true
    false
    false
  
  
  
  14.2 Elementary Operations for Integers
  
  14.2-1 IsInt
  
  IsInt( obj )  Category
  
  Every rational integer lies in the category IsInt, which is a subcategory of
  IsRat (17.2-1).
  
  14.2-2 IsPosInt
  
  IsPosInt( obj )  Category
  
  Every positive integer lies in the category IsPosInt.
  
  14.2-3 Int
  
  Int( elm )  attribute
  
  Int returns an integer int whose meaning depends on the type of elm.
  
  If elm is a rational number (see Chapter 17) then int is the integer part of
  the quotient of numerator and denominator of elm (see QuoInt (14.3-1)).
  
  If  elm  is  an element of a finite prime field (see Chapter 59) then int is
  the smallest nonnegative integer such that elm = int * One( elm ).
  
  If  elm is a string (see Chapter 27) consisting of digits '0', '1', ..., '9'
  and  '-'  (at  the first position) then int is the integer described by this
  string.  The  operation  String (27.7-6) can be used to compute a string for
  rational integers, in fact for all cyclotomics.
  
    Example  
    gap> Int( 4/3 );  Int( -2/3 );
    1
    0
    gap> int:= Int( Z(5) );  int * One( Z(5) );
    2
    Z(5)
    gap> Int( "12345" );  Int( "-27" );  Int( "-27/3" );
    12345
    -27
    fail
  
  
  14.2-4 IsEvenInt
  
  IsEvenInt( n )  function
  
  tests if the integer n is divisible by 2.
  
  14.2-5 IsOddInt
  
  IsOddInt( n )  function
  
  tests if the integer n is not divisible by 2.
  
  14.2-6 AbsInt
  
  AbsInt( n )  function
  
  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.
  
  AbsInt is a special case of the general operation EuclideanDegree (56.6-2).
  
  See also AbsoluteValue (18.1-8).
  
    Example  
    gap> AbsInt( 33 );
    33
    gap> AbsInt( -214378 );
    214378
    gap> AbsInt( 0 );
    0
  
  
  14.2-7 SignInt
  
  SignInt( n )  function
  
  SignInt returns the sign of the integer n, i.e., 1 if n is positive, -1 if n
  is negative and 0 if n is 0.
  
    Example  
    gap> SignInt( 33 );
    1
    gap> SignInt( -214378 );
    -1
    gap> SignInt( 0 );
    0
  
  
  14.2-8 LogInt
  
  LogInt( n, base )  function
  
  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  e such that base^e ≤ n. The function LogInt will signal an error if
  either n or base is not positive.
  
  For   base   =  2  this  is  very  efficient  because  the  internal  binary
  representation of the integer is used.
  
    Example  
    gap> LogInt( 1030, 2 );
    10
    gap> 2^10;
    1024
    gap> LogInt( 1, 10 );
    0
  
  
  14.2-9 RootInt
  
  RootInt( n[, k] )  function
  
  RootInt  returns  the  integer part of the kth 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 n is negative and k is odd RootInt returns -RootInt( -n, k ). If
  n  is  negative and k is even RootInt will cause an error. RootInt will also
  cause an error if k is 0 or negative.
  
    Example  
    gap> RootInt( 361 );
    19
    gap> RootInt( 2 * 10^12 );
    1414213
    gap> RootInt( 17000, 5 );
    7
    gap> 7^5;
    16807
  
  
  14.2-10 SmallestRootInt
  
  SmallestRootInt( n )  function
  
  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.
  
    Example  
    gap> SmallestRootInt( 2^30 );
    2
    gap> SmallestRootInt( -(2^30) );
    -4
  
  
  Note that (-2)^30 = +(2^30).
  
    Example  
    gap> SmallestRootInt( 279936 );
    6
    gap> LogInt( 279936, 6 );
    7
    gap> SmallestRootInt( 1001 );
    1001
  
  
  14.2-11 ListOfDigits
  
  ListOfDigits( n )  function
  
  For  a  positive integer n this function returns a list l, consisting of the
  digits of n in decimal representation.
  
    Example  
    gap> ListOfDigits(3142);   
    [ 3, 1, 4, 2 ]
  
  
  14.2-12 Random
  
  Random( Integers )  method
  
  Random  for  integers  returns  pseudo  random  integers  between -10 and 10
  distributed  according  to  a  binomial  distribution. To generate uniformly
  distributed  integers  from  a  range, use the construction Random( [ low ..
  high ] )  (see Random (30.7-1)).
  
  
  14.3 Quotients and Remainders
  
  14.3-1 QuoInt
  
  QuoInt( n, m )  function
  
  QuoInt returns the integer part of the quotient of its integer operands.
  
  If  n and m are positive, QuoInt returns the largest positive integer q such
  that  q  *  m  ≤ n. If n or m or both are negative the absolute value of the
  integer part of the quotient is the quotient of the absolute values of n and
  m, and the sign of it is the product of the signs of n and m.
  
  QuoInt  is  used  in  a  method  for the general operation EuclideanQuotient
  (56.6-3).
  
    Example  
    gap> QuoInt(5,3);  QuoInt(-5,3);  QuoInt(5,-3);  QuoInt(-5,-3);
    1
    -1
    -1
    1
  
  
  14.3-2 BestQuoInt
  
  BestQuoInt( n, m )  function
  
  BestQuoInt  returns the best quotient q of the integers n and m. This is the
  quotient  such  that  n-q*m  has  minimal  absolute  value. If there are two
  quotients  whose  remainders have the same absolute value, then the quotient
  with the smaller absolute value is chosen.
  
    Example  
    gap> BestQuoInt( 5, 3 );  BestQuoInt( -5, 3 );
    2
    -2
  
  
  14.3-3 RemInt
  
  RemInt( n, m )  function
  
  RemInt returns the remainder of its two integer operands.
  
  If  m is not equal to zero, RemInt returns n - m * QuoInt( n, m ). Note that
  the  rules  given  for QuoInt (14.3-1) imply that the return value of RemInt
  has  the  same  sign  as  n and its absolute value is strictly less than the
  absolute  value  of  m.  Note also that the return value equals n mod m when
  both n and m are nonnegative. Dividing by 0 signals an error.
  
  RemInt  is  used  in  a  method for the general operation EuclideanRemainder
  (56.6-4).
  
    Example  
    gap> RemInt(5,3);  RemInt(-5,3);  RemInt(5,-3);  RemInt(-5,-3);
    2
    -2
    2
    -2
  
  
  14.3-4 GcdInt
  
  GcdInt( m, n )  function
  
  GcdInt returns the greatest common divisor of its two integer operands m and
  n, i.e., the greatest integer that divides both m and n. The greatest common
  divisor is never negative, even if the arguments are. We define GcdInt( m, 0
  ) = GcdInt( 0, m ) = AbsInt( m ) and GcdInt( 0, 0 ) = 0.
  
  GcdInt is a method used by the general function Gcd (56.7-1).
  
    Example  
    gap> GcdInt( 123, 66 );
    3
  
  
  14.3-5 Gcdex
  
  Gcdex( m, n )  function
  
  returns  a record g describing the extended greatest common divisor of m and
  n.  The  component  gcd  is  this  gcd, the components coeff1 and coeff2 are
  integer  cofactors  such  that  g.gcd = g.coeff1 * m + g.coeff2 * n, and the
  components  coeff3 and coeff4 are integer cofactors such that 0 = g.coeff3 *
  m + g.coeff4 * n.
  
  If  m  and  n  both are nonzero, AbsInt( g.coeff1 ) is less than or equal to
  AbsInt(n)  /  (2  *  g.gcd), and AbsInt( g.coeff2 ) is less than or equal to
  AbsInt(m) / (2 * g.gcd).
  
  If m or n or both are zero coeff3 is -n / g.gcd and coeff4 is m / 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.
  
    Example  
    gap> Gcdex( 123, 66 );
    rec( coeff1 := 7, coeff2 := -13, coeff3 := -22, coeff4 := 41, 
      gcd := 3 )
  
  
  This means 3 = 7 * 123 - 13 * 66, 0 = -22 * 123 + 41 * 66.
  
    Example  
    gap> Gcdex( 0, -3 );
    rec( coeff1 := 0, coeff2 := -1, coeff3 := 1, coeff4 := 0, gcd := 3 )
    gap> Gcdex( 0, 0 );
    rec( coeff1 := 1, coeff2 := 0, coeff3 := 0, coeff4 := 1, gcd := 0 )
  
  
  GcdRepresentation  (56.7-3)  provides  similar  functionality over arbitrary
  Euclidean rings.
  
  14.3-6 LcmInt
  
  LcmInt( m, n )  function
  
  returns the least common multiple of the integers m and n.
  
  LcmInt is a method used by the general operation Lcm (56.7-6).
  
    Example  
    gap> LcmInt( 123, 66 );
    2706
  
  
  14.3-7 CoefficientsQadic
  
  CoefficientsQadic( i, q )  operation
  
  returns  the  q-adic  representation  of  the  integer  i  as  a  list  l of
  coefficients  satisfying  the  equality  i  =  ∑_{j = 0} q^j ⋅ l[j+1] for an
  integer q > 1.
  
    Example  
    gap> l:=CoefficientsQadic(462,3);
    [ 0, 1, 0, 2, 2, 1 ]
  
  
  14.3-8 CoefficientsMultiadic
  
  CoefficientsMultiadic( ints, int )  function
  
  returns the multiadic expansion of the integer int modulo the integers given
  in  ints  (in  ascending  order).  It  returns a list of coefficients in the
  reverse order to that in ints.
  
  14.3-9 ChineseRem
  
  ChineseRem( moduli, residues )  function
  
  ChineseRem  returns the combination of the residues modulo the moduli, i.e.,
  the  unique  integer  c  from  [0..Lcm(moduli)-1]  such that c = residues[i]
  modulo  moduli[i]  for  all  i,  if it exists. If no such combination exists
  ChineseRem signals an error.
  
  Such  a  combination does exist if and only if residues[i] = residues[k] mod
  Gcd( moduli[i], moduli[k] ) for every pair 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.
  
    Example  
    gap> ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] );
    53
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] );
    103
  
  
    Example  
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] );
    Error, the residues must be equal modulo 2 called from
    <function>( <arguments> ) called from read-eval-loop
    Entering break read-eval-print loop ...
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk> gap> 
  
  
  14.3-10 PowerModInt
  
  PowerModInt( r, e, m )  function
  
  returns r^e mod m for integers r, e and m (e ≥ 0).
  
  Note  that  PowerModInt  can  reduce  intermediate  results  and  thus  will
  generally  be faster than using r^e mod m, which would compute r^e first and
  reduces the result afterwards.
  
  PowerModInt is a method for the general operation PowerMod (56.7-9).
  
  
  14.4 Prime Integers and Factorization
  
  14.4-1 Primes
  
  Primes global variable
  
  Primes is a strictly sorted list of the 168 primes less than 1000.
  
  This  is  used  in  IsPrimeInt  (14.4-2) and FactorsInt (14.4-7) to cast out
  small primes quickly.
  
    Example  
    gap> Primes[1];
    2
    gap> Primes[100];
    541
  
  
  14.4-2 IsPrimeInt
  
  IsPrimeInt( n )  function
  IsProbablyPrimeInt( n )  function
  
  IsPrimeInt returns false if it can prove that the integer 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 every prime n. IsPrimeInt will return false
  for  all  composite n < 10^18 and for all composite n that have a factor p <
  1000.  So  for integers n < 10^18, IsPrimeInt is a proper primality test. It
  is conceivable that IsPrimeInt may return true for some composite n > 10^18,
  but no such n is currently known. So for integers n > 10^18, IsPrimeInt is a
  probable-primality  test.  IsPrimeInt will issue a warning when its argument
  is  probably  prime but not a proven prime. (The function IsProbablyPrimeInt
  will  do  a similar calculation but not issue a warning.) The warning can be
  switched  off  by  SetInfoLevel(  InfoPrimeInt, 0 );, the default level is 1
  (also see SetInfoLevel (7.4-3) ).
  
  If  composites  that fool IsPrimeInt do exist, they would be extremely rare,
  and  finding  one  by pure chance might be less likely than finding a bug in
  GAP.  We  would  appreciate  being informed about any example of a composite
  number n for which IsPrimeInt returns true.
  
  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
  primality.gi.
  
  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.
  
  IsPrimeInt is a method for the general operation IsPrime (56.5-8).
  
  Remark:  In  future  versions  of  GAP  we  hope to change the definition of
  IsPrimeInt  to  return  true  only  for  proven primes (currently, we lack a
  sufficiently   good   primality  proving  function).  In  applications,  use
  explicitly IsPrimeInt or IsProbablyPrimeInt with this change in mind.
  
    Example  
    gap> IsPrimeInt( 2^31 - 1 );
    true
    gap> IsPrimeInt( 10^42 + 1 );
    false
  
  
  14.4-3 PrimalityProof
  
  PrimalityProof( n )  function
  
  Construct  a  machine  verifiable  proof  of  the primality of (the probable
  prime)  n,  following  the  ideas  of [BLS75]. The proof consists of various
  Fermat  and  Lucas  pseudoprimality  tests, which taken as a whole prove the
  primality. The proof is represented as a list of witnesses of two kinds. The
  first   kind,  [  "F",  divisor,  base  ],  indicates  a  successful  Fermat
  pseudoprimality test, where n is a strong pseudoprime at base with order not
  divisible by (n-1)/divisor. The second kind, [ "L", divisor, discriminant, P
  ] indicates a successful Lucas pseudoprimality test, for a quadratic form of
  given discriminant and middle term P with an extra check at (n+1)/divisor.
  
  14.4-4 IsPrimePowerInt
  
  IsPrimePowerInt( n )  function
  
  IsPrimePowerInt  returns  true  if  the integer n is a prime power and false
  otherwise.
  
  An  integer  n  is  a  prime  power if there exists a prime p and a positive
  integer  i  such  that p^i = n. If n is negative the condition is that there
  must  exist a negative prime p and an odd positive integer i such that p^i =
  n. The integers 1 and -1 are not prime powers.
  
  Note   that   IsPrimePowerInt   uses   SmallestRootInt   (14.2-10)   and   a
  probable-primality test (see IsPrimeInt (14.4-2)).
  
    Example  
    gap> IsPrimePowerInt( 31^5 );
    true
    gap> IsPrimePowerInt( 2^31-1 );  # 2^31-1 is actually a prime
    true
    gap> IsPrimePowerInt( 2^63-1 );
    false
    gap> Filtered( [-10..10], IsPrimePowerInt );
    [ -8, -7, -5, -3, -2, 2, 3, 4, 5, 7, 8, 9 ]
  
  
  14.4-5 NextPrimeInt
  
  NextPrimeInt( n )  function
  
  NextPrimeInt  returns  the  smallest prime which is strictly larger than the
  integer n.
  
  Note  that  NextPrimeInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).
  
    Example  
    gap> NextPrimeInt( 541 ); NextPrimeInt( -1 );
    547
    2
  
  
  14.4-6 PrevPrimeInt
  
  PrevPrimeInt( n )  function
  
  PrevPrimeInt  returns  the  largest prime which is strictly smaller than the
  integer n.
  
  Note  that  PrevPrimeInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).
  
    Example  
    gap> PrevPrimeInt( 541 ); PrevPrimeInt( 1 );
    523
    -2
  
  
  14.4-7 FactorsInt
  
  FactorsInt( n )  function
  FactorsInt( n: RhoTrials := trials )  function
  
  FactorsInt returns a list of factors of a given integer n such that Product(
  FactorsInt(  n  )  ) = n. If |n| ≤ 1 the list [n] is returned. Otherwise the
  result  contains probable primes, sorted by absolute value. The entries will
  all be positive except for the first one in case of a negative n.
  
  See  PrimeDivisors  (14.4-8) for a function that returns a set of (probable)
  primes dividing n.
  
  Note   that   FactorsInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).  Thus  FactorsInt  might  return  a list which contains composite
  integers.  In such a case you will get a warning about the use of a probable
  prime. You can switch off these warnings by SetInfoLevel( InfoPrimeInt, 0 );
  (also see SetInfoLevel (7.4-3)).
  
  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  10^10. If n contains multiple factors
  larger than that FactorsInt may not be able to factor n and will then signal
  an error.
  
  FactorsInt is used in a method for the general operation Factors (56.5-9).
  
  In  the  second  form, FactorsInt calls FactorsRho with a limit of trials on
  the  number  of trials it performs. The default is 8192. Note that Pollard's
  Rho  is  the  fastest  method  for  finding  prime factors with roughly 5-10
  decimal  digits,  but  becomes more and more inferior to other factorization
  techniques  like  e.g. the Elliptic Curves Method (ECM) the bigger the prime
  factors are. Therefore instead of performing a huge number of Rho trials, it
  is  usually more advisable to install the FactInt package and then simply to
  use  the  operation  Factors  (56.5-9). The factorization of the 8-th Fermat
  number by Pollard's Rho below takes already a while.
  
    Example  
    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 ]
    gap> FactorsInt(2^256+1:RhoTrials:=100000000);
    [ 1238926361552897, 
      93461639715357977769163558199606896584051237541638188580280321 ]
  
  
  14.4-8 PrimeDivisors
  
  PrimeDivisors( n )  attribute
  
  PrimeDivisors  returns  for  a  non-zero  integer  n  a  set of its positive
  (probable)  primes  divisors.  In  rare  cases  the  result  could contain a
  composite    number    which    passed    certain   primality   tests,   see
  IsProbablyPrimeInt (14.4-2) and FactorsInt (14.4-7) for more details.
  
    Example  
    gap> PrimeDivisors(-12);
    [ 2, 3 ]
    gap> PrimeDivisors(1);
    [  ]
  
  
  14.4-9 PartialFactorization
  
  PartialFactorization( n[, effort] )  operation
  
  PartialFactorization  returns  a  partial factorization of the integer n. No
  assertions  are  made  about  the  primality of the factors, except of those
  mentioned below.
  
  The argument effort, if given, specifies how intensively the function should
  try to determine factors of n. The default is effort = 5.
  
      If  effort = 0,  trial  division  by  the  primes  below  100 is done.
        Returned factors below 10^4 are guaranteed to be prime.
  
      If  effort = 1,  trial  division  by  the  primes  below 1000 is done.
        Returned factors below 10^6 are guaranteed to be prime.
  
      If effort = 2, additionally trial division by the numbers in the lists
        Primes2  and ProbablePrimes2 is done, and perfect powers are detected.
        Returned factors below 10^6 are guaranteed to be prime.
  
      If  effort = 3, additionally FactorsRho (Pollard's Rho) with RhoTrials
        = 256 is used.
  
      If effort = 4, as above, but RhoTrials = 2048.
  
      If  effort = 5, as above, but RhoTrials = 8192. Returned factors below
        10^12 are guaranteed to be prime, and all prime factors below 10^6 are
        guaranteed to be found.
  
      If  effort = 6  and  the package FactInt is loaded, in addition to the
        above quite a number of special cases are handled.
  
      If  effort = 7 and the package FactInt is loaded, the only thing which
        is    not    attempted   to   obtain   a   full   factorization   into
        Baillie-Pomerance-Selfridge-Wagstaff  pseudoprimes  is the application
        of the MPQS to a remaining composite with more than 50 decimal digits.
  
  Increasing  the  value  of  the argument effort by one usually results in an
  increase of the runtime requirements by a factor of (very roughly!) 3 to 10.
  (Also see CheapFactorsInt (EDIM: CheapFactorsInt)).
  
    Example  
    gap> List([0..5],i->PartialFactorization(97^35-1,i)); 
    [ [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 
          2446338959059521520901826365168917110105972824229555319002965029 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 
          2529823122088440042297648774735177983563570655873376751812787 ],
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 
          2529823122088440042297648774735177983563570655873376751812787 ],
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 
          242549173950325921859769421435653153445616962914227 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121, 
          352993394104278463123335513593170858474150787 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121, 
          20241187, 504769301, 34549173843451574629911361501 ] ]
  
  
  14.4-10 PrintFactorsInt
  
  PrintFactorsInt( n )  function
  
  prints the prime factorization of the integer n in human-readable form.
  
    Example  
    gap> PrintFactorsInt( Factorial( 7 ) ); Print( "\n" );
    2^4*3^2*5*7
  
  
  14.4-11 PrimePowersInt
  
  PrimePowersInt( n )  function
  
  returns  the prime factorization of the integer n as a list [ p_1, e_1, ...,
  p_k, e_k ] with n = p_1^{e_1} ⋅ p_2^{e_2} ⋅ ... ⋅ p_k^{e_k}.
  
    Example  
    gap> PrimePowersInt( Factorial( 7 ) );
    [ 2, 4, 3, 2, 5, 1, 7, 1 ]
  
  
  14.4-12 DivisorsInt
  
  DivisorsInt( n )  function
  
  DivisorsInt  returns  a  list  of all divisors of the integer n. The list is
  sorted,  so  that  it  starts  with  1  and  ends  with  n.  We  define that
  DivisorsInt( -n ) = DivisorsInt( n ).
  
  Since  the  set of divisors of 0 is infinite calling DivisorsInt( 0 ) causes
  an error.
  
  DivisorsInt  may call FactorsInt (14.4-7) to obtain the prime factors. Sigma
  (15.5-1)  and  Tau  (15.5-2)  compute  the  sum  and  the number of positive
  divisors, respectively.
  
    Example  
    gap> DivisorsInt( 1 ); DivisorsInt( 20 ); DivisorsInt( 541 );
    [ 1 ]
    [ 1, 2, 4, 5, 10, 20 ]
    [ 1, 541 ]
  
  
  
  14.5 Residue Class Rings
  
  ZmodnZ  (14.5-2)  returns  a  residue  class ring of Integers (14) modulo an
  ideal.  These  residue  class rings are rings, thus all operations for rings
  (see Chapter 56) apply. See also Chapters 59 and 15.
  
  14.5-1 \mod
  
  \mod( r/s, n )  operation
  
  If  r, s and n are integers, r / s as a reduced fraction is p/q, where q and
  n  are  coprime,  then r / s mod n is defined to be the product of p and the
  inverse of q modulo n. See Section 4.13 for more details and definitions.
  
  With the above definition, 4 / 6 mod 32 equals 2 / 3 mod 32 and hence exists
  (and is equal to 22), despite the fact that 6 has no inverse modulo 32.
  
  14.5-2 ZmodnZ
  
  ZmodnZ( n )  function
  ZmodpZ( p )  function
  ZmodpZNC( p )  function
  
  ZmodnZ returns a ring R isomorphic to the residue class ring of the integers
  modulo  the  ideal  generated by n. The element corresponding to the residue
  class  of  the integer i in this ring can be obtained by i * One( R ), and a
  representative  of  the residue class corresponding to the element x ∈ R can
  be computed by Int( x ).
  
  ZmodnZ( n ) is equal to Integers mod n.
  
  ZmodpZ  does the same if the argument p is a prime integer, additionally the
  result is a field. ZmodpZNC omits the check whether p is a prime.
  
  Each  ring  returned  by  these  functions  contains the whole family of its
  elements  if  n  is  not  a prime, and is embedded into the family of finite
  field elements of characteristic n if n is a prime.
  
  14.5-3 ZmodnZObj
  
  ZmodnZObj( Fam, r )  operation
  ZmodnZObj( r, n )  operation
  
  If  the  first argument is a residue class family Fam then ZmodnZObj returns
  the element in Fam whose coset is represented by the integer r.
  
  If  the  two  arguments  are  an  integer  r  and  a positive integer n then
  ZmodnZObj  returns  the  element  in ZmodnZ( n ) (see ZmodnZ (14.5-2)) whose
  coset is represented by the integer r.
  
    Example  
    gap> r:= ZmodnZ(15);
    (Integers mod 15)
    gap> fam:=ElementsFamily(FamilyObj(r));;
    gap> a:= ZmodnZObj(fam,9);
    ZmodnZObj( 9, 15 )
    gap> a+a;
    ZmodnZObj( 3, 15 )
    gap> Int(a+a);
    3
  
  
  14.5-4 IsZmodnZObj
  
  IsZmodnZObj( obj )  Category
  IsZmodnZObjNonprime( obj )  Category
  IsZmodpZObj( obj )  Category
  IsZmodpZObjSmall( obj )  Category
  IsZmodpZObjLarge( obj )  Category
  
  The elements in the rings Z / n Z are in the category IsZmodnZObj. If n is a
  prime  then  the elements are of course also in the category IsFFE (59.1-1),
  otherwise they are in IsZmodnZObjNonprime. IsZmodpZObj is an abbreviation of
  IsZmodnZObj   and   IsFFE.   This   category   is   the  disjoint  union  of
  IsZmodpZObjSmall  and  IsZmodpZObjLarge,  the former containing all elements
  with n at most MAXSIZE_GF_INTERNAL.
  
  The reasons to distinguish the prime case from the nonprime case are
  
      that  objects  in  IsZmodnZObjNonprime have an external representation
        (namely the residue in the range [ 0, 1, ..., n-1 ]),
  
      that  the  comparison  of elements can be defined as comparison of the
        residues, and
  
      that  the  elements  lie in a family of type IsZmodnZObjNonprimeFamily
        (note that for prime n, the family must be an IsFFEFamily).
  
  The reasons to distinguish the small and the large case are that for small n
  the  elements  must be compatible with the internal representation of finite
  field  elements,  whereas  we are free to define comparison as comparison of
  residues for large n.
  
  Note  that we cannot claim that every finite field element of degree 1 is in
  IsZmodnZObj,  since finite field elements in internal representation may not
  know that they lie in the prime field.
  
  
  14.6 Check Digits
  
  14.6-1 CheckDigitISBN
  
  CheckDigitISBN( n )  function
  CheckDigitISBN13( n )  function
  CheckDigitPostalMoneyOrder( n )  function
  CheckDigitUPC( n )  function
  
  These  functions  can  be  used  to compute, or check, check digits for some
  everyday items. In each case what is submitted as input is either the number
  with  check digit (in which case the function returns true or false), or the
  number  without  check digit (in which case the function returns the missing
  check digit). The number can be specified as integer, as string (for example
  in case of leading zeros) or as a sequence of arguments, each representing a
  single  digit.  The check digits tested are the 10-digit ISBN (International
  Standard Book Number) using CheckDigitISBN (since arithmetic is module 11, a
  digit  11  is  represented  by  an  X);  the  newer  13-digit  ISBN-13 using
  CheckDigitISBN13;  the  numbers  of  11-digit  US  postal money orders using
  CheckDigitPostalMoneyOrder; and the 12-digit UPC bar code found on groceries
  using CheckDigitUPC.
  
    Example  
    gap> CheckDigitISBN("052166103");
    Check Digit is 'X'
    'X'
    gap> CheckDigitISBN("052166103X");
    Checksum test satisfied
    true
    gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,1);
    Checksum test failed
    false
    gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,'X'); # note single quotes!
    Checksum test satisfied
    true
    gap> CheckDigitISBN13("9781420094527");
    Checksum test satisfied
    true
    gap> CheckDigitUPC("07164183001");
    Check Digit is 1
    1
    gap> CheckDigitPostalMoneyOrder(16786457155);
    Checksum test satisfied
    true
  
  
  14.6-2 CheckDigitTestFunction
  
  CheckDigitTestFunction( l, m, f )  function
  
  This  function  creates  check  digit  test functions such as CheckDigitISBN
  (14.6-1)  for  check  digit schemes that use the inner products with a fixed
  vector  modulo  a  number.  The  scheme creates will use strings of l digits
  (including  the  check  digits),  the  check consists of taking the standard
  product of the vector of digits with the fixed vector f modulo m; the result
  needs  to  be  0.  The function returns a function that then can be used for
  testing or determining check digits.
  
    Example  
    gap> isbntest:=CheckDigitTestFunction(10,11,[1,2,3,4,5,6,7,8,9,-1]); 
    function( arg... ) ... end
    gap> isbntest("038794680");
    Check Digit is 2
    2
  
  
  
  14.7 Random Sources
  
  GAP  provides  Random (30.7-1) methods for many collections of objects. On a
  lower  level  these methods use random sources which provide random integers
  and random choices from lists.
  
  14.7-1 IsRandomSource
  
  IsRandomSource( obj )  Category
  
  This is the category of random source objects which are defined to have, for
  an  object  rs  in  this  category,  methods  available  for  the  following
  operations  which  are  explained  in  more detail below: Random( rs, list )
  giving  a  random element of a list, Random( rs, low, high ) giving a random
  integer  between low and high (inclusive), Init (14.7-3), State (14.7-3) and
  Reset (14.7-3).
  
  Use RandomSource (14.7-5) to construct new random sources.
  
  One  idea behind providing several independent (pseudo) random sources is to
  make  algorithms  which  use some sort of random choices deterministic. They
  can  use  their  own  new  random source created with a fixed seed and so do
  exactly the same in different calls.
  
  Random source objects lie in the family RandomSourcesFamily.
  
  14.7-2 Random
  
  Random( rs, list )  operation
  Random( rs, low, high )  operation
  
  This operation returns a random element from list list, or an integer in the
  range from the given (possibly large) integers low to high, respectively.
  
  The  choice should only depend on the random source rs and have no effect on
  other random sources.
  
    Example  
    gap> mysource := RandomSource(IsMersenneTwister, 42);;
    gap> Random(mysource, 1, 10^60);
    999331861769949319194941485000557997842686717712198687315183
  
  
  14.7-3 State
  
  State( rs )  operation
  Reset( rs[, seed] )  operation
  Init( prers[, seed] )  operation
  
  These  are the basic operations for which random sources (see IsRandomSource
  (14.7-1)) must have methods.
  
  State  should  return  a data structure which allows to recover the state of
  the  random  source  such  that a sequence of random calls using this random
  source  can  be reproduced. If a random source cannot be reset (say, it uses
  truly random physical data) then State should return fail.
  
  Reset(  rs, seed ) resets the random source rs to a state described by seed,
  if  the  random  source  can be reset (otherwise it should do nothing). Here
  seed  can  be  an output of State and then should reset to that state. Also,
  the  methods should always allow integers as seed. Without the seed argument
  the default seed = 1 is used.
  
  Init  is  the  constructor  of  a  random source, it gets an empty component
  object  prers  which  has  already  the  correct type and should fill in the
  actual  data  which are needed. Optionally, it should allow one to specify a
  seed for the initial state, as explained for Reset.
  
  Most   methods   for   Random   (30.7-1)   in   the   GAP  library  use  the
  GlobalMersenneTwister  (14.7-4)  as  random  source.  It can be reset into a
  known state as in the following example.
  
    Example  
    gap> seed := State(GlobalMersenneTwister);;
    gap> List([1..10],i->Random(Integers));
    [ 2, -1, -2, -1, -1, 1, -4, 1, 0, -1 ]
    gap> List([1..10],i->Random(Integers));
    [ -1, -1, 1, -1, 1, -2, -1, -2, 0, -1 ]
    gap> Reset(GlobalMersenneTwister, seed);;
    gap> List([1..10],i->Random(Integers));
    [ 2, -1, -2, -1, -1, 1, -4, 1, 0, -1 ]
  
  
  14.7-4 IsMersenneTwister
  
  IsMersenneTwister( rs )  Category
  IsGAPRandomSource( rs )  Category
  IsGlobalRandomSource( rs )  Category
  GlobalMersenneTwister global variable
  GlobalRandomSource global variable
  
  Currently,   the  GAP  library  provides  three  types  of  random  sources,
  distinguished by the three listed categories.
  
  IsMersenneTwister are random sources which use a fast random generator of 32
  bit  numbers,  called the Mersenne twister. The pseudo random sequence has a
  period of 2^19937-1 and the numbers have a 623-dimensional equidistribution.
  For  more  details  and  the origin of the code used in the GAP kernel, see:
  http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html.
  
  Use  the  Mersenne  twister  if  possible, in particular for generating many
  large random integers.
  
  There  is also a predefined global random source GlobalMersenneTwister which
  is used by most of the library methods for Random (30.7-1).
  
  IsGAPRandomSource  uses  the  same number generator as IsGlobalRandomSource,
  but  you  can  create  several  of these random sources which generate their
  random numbers independently of all other random sources.
  
  IsGlobalRandomSource  gives  access to the classical global random generator
  which  was  used by GAP in former releases. You do not need to construct new
  random  sources  of  this  kind  which  would  all  use the same global data
  structure. Just use the existing random source GlobalRandomSource. This uses
  the  additive  random  number  generator  described  in [Knu98] (Algorithm A
  in 3.2.2 with lag 30).
  
  14.7-5 RandomSource
  
  RandomSource( cat[, seed] )  operation
  
  This  operation is used to create new random sources. The first argument cat
  is  the  category  describing  the type of the random generator, an optional
  seed  which can be an integer or a type specific data structure can be given
  to specify the initial state.
  
    Example  
    gap> rs1 := RandomSource(IsMersenneTwister);
    <RandomSource in IsMersenneTwister>
    gap> state1 := State(rs1);;
    gap> l1 := List([1..10000], i-> Random(rs1, [1..6]));;  
    gap> rs2 := RandomSource(IsMersenneTwister);;
    gap> l2 := List([1..10000], i-> Random(rs2, [1..6]));;
    gap> l1 = l2;
    true
    gap> l1 = List([1..10000], i-> Random(rs1, [1..6])); 
    false
    gap> n := Random(rs1, 1, 2^220);
    1077726777923092117987668044202944212469136000816111066409337432400