%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A integer.tex GAP documentation Martin Schoenert %% %A @(#)$Id: integer.tex,v 3.13.1.2 1994/08/30 11:40:35 mschoene Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file contains descriptions of the integer datatype, the operations %% and the functions. %% %H $Log: integer.tex,v $ %H Revision 3.13.1.2 1994/08/30 11:40:35 mschoene %H added yet another Mersenne prime exponent %H %H Revision 3.13.1.1 1994/08/24 16:02:21 mschoene %H changed the description of 'IsPrimeInt' %H %H Revision 3.13 1993/03/11 10:53:19 fceller %H added 'EuclideanQuotient', 'EuclideanRemainder' and 'QuotientRemainder' %H %H Revision 3.12 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.11 1993/02/18 15:06:02 felsch %H anothe example fixed %H %H Revision 3.10 1993/02/12 16:08:27 felsch %H more examples fixed %H %H Revision 3.9 1993/02/01 13:38:07 felsch %H examples fixed %H %H Revision 3.8 1992/04/06 16:26:54 martin %H fixed some more typos %H %H Revision 3.7 1992/04/02 21:06:23 martin %H changed *domain functions* to *set theoretic functions* %H %H Revision 3.6 1992/03/27 18:55:07 martin %H added another Mersenne prime exponent %H %H Revision 3.5 1991/12/30 09:29:21 martin %H changed incorrect reference to "SmallestRoot" %H %H Revision 3.4 1991/12/27 16:07:04 martin %H revised everything for GAP 3.1 manual %H %H Revision 3.3 1991/07/26 12:34:01 martin %H improved the index %H %H Revision 3.2 1991/07/26 09:01:07 martin %H changed |\GAP\ | to |{\GAP}| %H %H Revision 3.1 1991/07/25 16:16:59 martin %H fixed some minor typos %H %H Revision 3.0 1991/04/11 11:31:19 martin %H Initial revision under RCS %H %% \Chapter{Integers}% \index{type!integer} 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 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. | 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 {\GAP} 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\"'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Integers}% \index{comparisons!of integers} ' = ' \\ ' \<> ' The equality operator '=' evaluates to 'true' if the integer is equal to the integer and 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if is not equal to 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 | ' \<\ ' \\ ' \<= ' \\ ' > ' \\ ' >= ' The operators '\<', '\<=', '>', and '=>' evaluate to 'true' if the integer is less than, less than or equal to, greater than, or greater than or equal to the integer , 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Integers}% \index{operations!for integers} ' + ' The operator '+' evaluates to the sum of the two integers and . ' - ' The operator '-' evaluates to the difference of the two integers and . ' \*\ ' The operator '\*' evaluates to the product of the two integers and . ' / ' The operator '/' evaluates to the quotient of the two integers and . 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"). ' mod ' The operator 'mod' evaluates to the smallest positive representative of the residue class of the left operand modulo the right, i.e., ' mod ' is the unique in the range '[0 .. AbsInt()-1]' such that divides ' - '. If the right operand is 0 an error is signalled. The remainder of the division can be computed with 'RemInt' (see "RemInt"). ' \^\ ' The operator '\^' evaluates to the -th power of the integer . If is a positive integer then '\^' is '\* \* ..\* ' ( factors). If is a negative integer '\^' is defined as $1 / {^{-}}$. 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{QuoInt}% \index{integer part of a quotient} 'QuoInt( , )' 'QuoInt' returns the integer part of the quotient of its integer operands. If and are positive 'QuoInt( , )' is the largest positive integer such that '\* \<= '. If or or both are negative the absolute value of the integer part of the quotient is the quotient of the absolute values of and , and the sign of it is the product of the signs of and . '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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RemInt}% \index{remainder of a quotient} 'RemInt( , )' 'RemInt' returns the remainder of its two integer operands. If is not equal to zero 'RemInt( , ) = - \* QuoInt( , )'. Note that the rules given for 'QuoInt' (see "QuoInt") imply that 'RemInt( , )' has the same sign as and its absolute value is strictly less than the absolute value of . Dividing by 0 signals an error. | gap> RemInt(5,2); RemInt(-5,2); RemInt(5,-2); RemInt(-5,-2); 1 -1 1 -1 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsInt}% \index{test!for an integer} 'IsInt( )' 'IsInt' returns 'true' if , which can be an arbitrary object, is an integer and 'false' otherwise. 'IsInt' will signal an error if is an unbound variable. | gap> IsInt( 1 ); true gap> IsInt( IsInt ); false # 'IsInt' is a function, not an integer | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Int}% \index{convert!to an integer} 'Int( )' 'Int' converts an object to an integer. If is an integer 'Int' will simply return . If is a rational number (see "Rationals") 'Int' returns the unique integer that has the same sign as and the largest absolute value not larger than the absolute value of . If is an element of the prime field of a finite field , 'Int' returns the least positive integer such that '\* .one = ' (see "IntFFE"). If 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$ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AbsInt}% \index{absolute value of an integer} 'AbsInt( )' 'AbsInt' returns the absolute value of the integer , i.e., if is positive, - if is negative and 0 if is 0 (see "SignInt"). | gap> AbsInt( 33 ); 33 gap> AbsInt( -214378 ); 214378 gap> AbsInt( 0 ); 0 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SignInt}% \index{sign!of an integer} 'SignInt( )' 'SignInt' returns the sign of the integer , i.e., 1 if is positive, -1 if is negative and 0 if is 0 (see "AbsInt"). | gap> SignInt( 33 ); 1 gap> SignInt( -214378 ); -1 gap> SignInt( 0 ); 0 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ChineseRem}% \index{chinese remainder} 'ChineseRem( , )' 'ChineseRem' returns the combination of the modulo the , i.e., the unique integer from '[0..Lcm()-1]' such that ' = [i]' modulo '[i]' for all , if it exists. If no such combination exists 'ChineseRem' signals an error. Such a combination does exist if and only if\\ '[]=[]' mod 'Gcd([],[])' for every pair , . 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LogInt}% \index{logarithm of an integer} 'LogInt( , )' 'LogInt' returns the integer part of the logarithm of the positive integer with respect to the positive integer , i.e., the largest positive integer such that $base^{exp} \<= n$. 'LogInt' will signal an error if either or is not positive. | gap> LogInt( 1030, 2 ); 10 # $2^{10} = 1024$ gap> LogInt( 1, 10 ); 0 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RootInt}% \index{root!of an integer}\index{square root!of an integer} 'RootInt( )' \\ 'RootInt( , )' 'RootInt' returns the integer part of the th root of the integer . If the optional integer argument is not given it defaults to 2, i.e., 'RootInt' returns the integer part of the square root in this case. If is positive 'RootInt' returns the largest positive integer $r$ such that $r^k \<= n$. If is negative and is odd 'RootInt' returns '-RootInt( -, )'. If is negative and is even 'RootInt' will cause an error. 'RootInt' will also cause an error if is 0 or negative. | gap> RootInt( 361 ); 19 gap> RootInt( 2 * 10^12 ); 1414213 gap> RootInt( 17000, 5 ); 7 # $7^5 = 16807$ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SmallestRootInt}% \index{root!of an integer, smallest} 'SmallestRootInt( )' 'SmallestRootInt' returns the smallest root of the integer . 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)^{30} = +(2^{30})$ gap> SmallestRootInt( 279936 ); 6 gap> LogInt( 279936, 6 ); 7 gap> SmallestRootInt( 1001 ); 1001 | '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: must be a primepower"); fi;| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Set Functions for Integers} 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( [ .. ] )'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Ring Functions for Integers} 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, )' This is implemented by 'IsPrimeInt', which you can call directly to save a little bit of time (see "IsPrimeInt"). 'Factors( Integers, )' This is implemented as by 'FactorsInt', which you can call directly to save a little bit of time (see "FactorsInt"). 'EuclideanDegree( Integers, )' 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, , )' This is implemented as 'RemInt( , )', which you can use directly to save a lot of time. 'EuclideanQuotient( Integers, , )' This is implemented as 'QuoInt( , )', which you can use directly to save a lot of time. 'QuotientRemainder( Integers, , )' This is implemented as '[ QuoInt(,), RemInt(,) ]', which you can use directly to save a lot of time. 'QuotientMod( Integers, , , )' This is implemented as '( / ) mod ', which you can use directly to save a lot of time. 'PowerMod( Integers, , , )' This is implemented by 'PowerModInt', which you can call directly to save a little bit of time. Note that using ' \^\ mod ' will generally be slower, because it can not reduce intermediate results like 'PowerMod'. 'Gcd( Integers, , .. )' 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( , )' 'Gcdex' returns a record. The component 'gcd' is the gcd of and . The components 'coeff1' and 'coeff2' are integer cofactors such that\\ '.gcd = .coeff1\* + .coeff2\*'.\\ If and both are nonzero, 'AbsInt( .coeff1 )' is less than or equal to 'AbsInt() / (2\*.gcd)' and 'AbsInt( .coeff2 )' is less than or equal to 'AbsInt() / (2\*.gcd)'. The components 'coeff3' and 'coeff4' are integer cofactors such that\\ '0 = .coeff3\* + .coeff4\*'.\\ If or or are both nonzero 'coeff3' is '- / .gcd' and 'coeff4' is ' / .gcd'. The coefficients always form a unimodular matrix, i.e., the determinant\\ '.coeff1\*.coeff4 - .coeff3\*.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, , .. )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Primes}% \index{list!of primes} 'Primes[ ]' '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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPrimeInt}% \index{test!for a prime} 'IsPrimeInt( )' 'IsPrimeInt' returns 'false' if it can prove that is composite and 'true' otherwise. By convention 'IsPrimeInt(0) = IsPrimeInt(1) = false' and we define 'IsPrimeInt( - ) = IsPrimeInt( )'. 'IsPrimeInt' will return 'true' for all prime $n$. 'IsPrimeInt' will return 'false' for all composite $n \< 10^{13}$ and for all composite $n$ that have a factor $p \< 1000$. So for integers $n \< 10^{13}$, 'IsPrimeInt' is a proper primality test. It is conceivable that 'IsPrimeInt' may return 'true' for some composite $n > 10^{13}$, but no such $n$ is currently known. So for integers $n > 10^{13}$, '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 {\GAP}. '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 . Testing numbers with several hundreds digits is quite feasible. | gap> IsPrimeInt( 2^31 - 1 ); true gap> IsPrimeInt( 10^42 + 1 ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPrimePowerInt}% \index{test!for a power of a prime} 'IsPrimePowerInt( )' 'IsPrimePowerInt' returns 'true' if the integer 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 $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$. 1 and -1 are not prime powers. 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 # $2^{31}-1$ is 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 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NextPrimeInt}% \index{larger prime} 'NextPrimeInt( )' 'NextPrimeInt' returns the smallest prime which is strictly larger than the integer . Note that 'NextPrimeInt' uses a probable-primality test (see "IsPrimeInt"). | gap> NextPrimeInt( 541 ); 547 gap> NextPrimeInt( -1 ); 2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PrevPrimeInt}% \index{smaller prime} 'PrevPrimeInt( )' 'PrevPrimeInt' returns the largest prime which is strictly smaller than the integer . Note that 'PrevPrimeInt' uses a probable-primality test (see "IsPrimeInt"). | gap> PrevPrimeInt( 541 ); 523 gap> PrevPrimeInt( 1 ); -2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{FactorsInt}% \index{factorization!of an integer} 'FactorsInt( )' 'FactorsInt' returns a list of the prime factors of the integer . If the th power of a prime divides this prime appears times. The list is sorted, that is the smallest prime factors come first. The first element has the same sign as , the others are positive. For any integer it holds that 'Product( FactorsInt( ) ) = '. 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 , 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 . 'FactorsInt' is guaranteed to find all factors less than $10^6$ and will find most factors less than $10^{10}$. If contains multiple factors larger than that 'FactorsInt' may not be able to factor and will then signal an error. | 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 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DivisorsInt}% \index{divisors!of an integer} 'DivisorsInt( )' 'DivisorsInt' returns a list of all positive *divisors* of the integer . The list is sorted, so it starts with 1 and ends with . We define 'DivisorsInt( - ) = DivisorsInt( )'. Since the set of divisors of 0 is infinite calling '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 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Sigma}% \index{sum!of divisors of an integer}% \index{mersenne primes}\index{primes!mersenne} 'Sigma( )' 'Sigma' returns the sum of the positive divisors (see "DivisorsInt") of the integer . 'Sigma' is a multiplicative arithmetic function, i.e., if $n$ and $m$ are relatively prime we have $\sigma(n m) = \sigma(n) \sigma(m)$. Together with the formula $\sigma(p^e) = (p^{e+1}-1) / (p-1)$ this allows you to compute $\sigma(n)$. Integers $n$ for which $\sigma(n)=2 n$ are called perfect. Even perfect integers are exactly of the form $2^{n-1}(2^n-1)$ where $2^n-1$ is prime. Primes of the form $2^n-1$ are called *Mersenne primes*, the known ones are obtained for $n =$ 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, and 859433. It is not known whether odd perfect integers exist, however \cite{BC89} show that any such integer must have at least 300 decimal digits. 'Sigma' usually spends most of its time factoring (see "FactorsInt"). | gap> Sigma( 0 ); Error, Sigma: 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Tau}% \index{number!of divisors of an integer} 'Tau( )' 'Tau' returns the number of the positive divisors (see "DivisorsInt") of the integer . 'Tau' is a multiplicative arithmetic function, i.e., if $n$ and $m$ are relatively prime we have $\tau(n m) = \tau(n) \tau(m)$. Together with the formula $\tau(p^e) = e+1$ this allows us to compute $\tau(n)$. 'Tau' usually spends most of its time factoring (see "FactorsInt"). | gap> Tau( 0 ); Error, Tau: 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 # $\tau(n)$ is odd if and only if $n$ is a perfect square | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MoebiusMu}% \index{Moebius inversion function} 'MoebiusMu( )' 'MoebiusMu' computes the value of the *Moebius function* for the integer . This is 0 for integers which are not squarefree, i.e., which are divisible by a square $r^2$. Otherwise it is 1 if has an even number and -1 if has an odd number of prime factors. The importance of $\mu$ stems from the so called inversion formula. Suppose $f(n)$ is a function defined on the positive integers and let $g(n)=\sum_{d \mid n}{f(d)}$. Then $f(n)=\sum_{d \mid n}{\mu(d) g(n/d)}$. As a special case we have $\phi(n) = \sum_{d \mid n}{\mu(d) n/d}$ since $n = \sum_{d \mid n}{\phi(d)}$ (see "Phi"). 'MoebiusMu' usually spends all of its time factoring (see "FactorsInt"). | gap> MoebiusMu( 60 ); 0 gap> MoebiusMu( 61 ); -1 gap> MoebiusMu( 62 ); 1 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%