GAP provides a couple of elementary number theoretic functions. Most of these deal with the group of integers coprime to m, called the prime residue group. f(m) (see Phi) is the order of this group, l(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order f(m), are called primitive roots (see PrimitiveRootMod, IsPrimitiveRootMod).
Note that neither the arguments nor the return values of the functions listed below are groups or group elements in the sense of GAP. The arguments are simply integers.
InfoNumtheor V
InfoNumtheor is the info class (see Info Functions) for the
functions in the number theory chapter.
PrimeResidues( m ) F
PrimeResidues returns the set of integers from the range 0..Abs(m)-1
that are coprime to the integer m.
Abs(m) must be less than 228, otherwise the set would probably be
too large anyhow.
gap> PrimeResidues( 0 ); PrimeResidues( 1 ); PrimeResidues( 20 ); [ ] [ 0 ] [ 1, 3, 7, 9, 11, 13, 17, 19 ]
Phi( m ) F
Phi returns the number f(m ) of positive integers less than the
positive integer m that are coprime to m.
Suppose that m = p1e1 p2e2 ¼pkek. Then f(m) is p1e1-1 (p1-1) p2e2-1 (p2-1) ¼pkek-1 (pk-1).
gap> Phi( 12 ); Phi( 2^13-1 ); Phi( 2^15-1 ); 4 8190 # which proves that 2^(13)-1 is a prime 27000
Lambda( m ) F
Lambda returns the exponent l(m ) of the group of prime
residues modulo the integer m.
l(m ) is the smallest positive integer l such that for every a relatively prime to m we have al º 1 mod m . Fermat's theorem asserts af(m ) º 1 mod m ; thus l(m) divides f(m) (see Phi).
Carmichael's theorem states that l can be computed as follows: l(2) = 1, l(4) = 2 and l(2e) = 2e-2 if 3 £ e, l(pe) = (p-1) pe-1 (i.e. f(m)) if p is an odd prime and l(n*m) = Lcm( l(n), l(m) ) if n, m are coprime.
Composites for which l(m) divides m - 1 are called Carmichaels. If 6k+1, 12k+1 and 18k+1 are primes their product is such a number. There are only 1547 Carmichaels below 1010 but 455052511 primes.
gap> Lambda( 10 ); 4 gap> Lambda( 30 ); 4 gap> Lambda( 561 ); 80 # 561 is the smallest Carmichael number
GeneratorsPrimeResidues( n ) F
Let n be a positive integer.
GeneratorsPrimeResidues returns a description of generators of the
group of prime residues modulo n.
The return value is a record with components
primes:
exponents:
generators:
gap> GeneratorsPrimeResidues( 1 ); rec( primes := [ ], exponents := [ ], generators := [ ] ) gap> GeneratorsPrimeResidues( 4*3 ); rec( primes := [ 2, 3 ], exponents := [ 2, 1 ], generators := [ 7, 5 ] ) gap> GeneratorsPrimeResidues( 8*9*5 ); rec( primes := [ 2, 3, 5 ], exponents := [ 3, 2, 1 ], generators := [ [ 271, 181 ], 281, 217 ] )
OrderMod( n, m ) F
OrderMod returns the multiplicative order of the integer n modulo the
positive integer m.
If n and m are not coprime the order of n is not defined
and OrderMod will return 0.
If n and m are relatively prime the multiplicative order of n modulo m is the smallest positive integer i such that n i º 1 mod m . If the group of prime residues modulo m is cyclic then each element of maximal order is called a primitive root modulo m (see IsPrimitiveRootMod).
OrderMod usually spends most of its time factoring m and f(m )
(see FactorsInt).
gap> OrderMod( 2, 7 ); OrderMod( 3, 7 ); 3 6 # 3 is a primitive root modulo 7
LogMod( n, r, m ) F
computes the discrete r-logarithm of the integer n modulo the integer
m.
It returns a number l such that r l º n mod m
if such a number exists.
Otherwise fail is returned.
At the moment only a very naive method has been implemented.
gap> l:= LogMod( 2, 5, 7 ); 5^l mod 7 = 2; 4 true gap> LogMod( 1, 3, 3 ); LogMod( 2, 3, 3 ); 0 fail
PrimitiveRootMod( m[, start] ) F
PrimitiveRootMod returns the smallest primitive root modulo the
positive integer m and fail if no such primitive root exists.
If the optional second integer argument start is given
PrimitiveRootMod returns the smallest primitive root that is strictly
larger than start.
gap> PrimitiveRootMod( 409 ); PrimitiveRootMod( 541, 2 ); 21 # largest primitive root for a prime less than 2000 10 gap> PrimitiveRootMod( 337, 327 ); PrimitiveRootMod( 30 ); fail # 327 is the largest primitive root mod 337 fail # there exists no primitive root modulo 30
IsPrimitiveRootMod( r, m ) F
IsPrimitiveRootMod returns true if the integer r is a primitive
root modulo the positive integer m and false otherwise. If r is
less than 0 or larger than m it is replaced by its remainder.
gap> IsPrimitiveRootMod( 2, 541 ); IsPrimitiveRootMod( -539, 541 ); true true # same computation as above gap> IsPrimitiveRootMod( 4, 541 ); false gap> ForAny( [1..29], r -> IsPrimitiveRootMod( r, 30 ) ); false # there does not exist a primitive root modulo 30
Jacobi( n, m ) F
Jacobi returns the value of the Jacobi symbol of the integer n
modulo the integer m.
Suppose that m = p1 p2 ¼pk is a product of primes, not necessarily distinct. Then for n coprime to m the Jacobi symbol is defined by J(n /m ) = L(n /p1) L(n /p2) ¼L(n /pk), where L(n /p) is the Legendre symbol (see Legendre). By convention J(n /1) = 1. If the gcd of n and m is larger than 1 we define J(n /m ) = 0.
If n is a quadratic residue modulo m, i.e., if there exists an r such that r2 º n mod m then J(n /m ) = 1. However, J(n /m ) = 1 implies the existence of such an r only if m is a prime.
Jacobi is very efficient, even for large values of n and m, it is
about as fast as the Euclidean algorithm (see Gcd).
gap> Jacobi( 11, 35 ); 1 # 9^2 = 11 mod 35 gap> Jacobi( 6, 35 ); -1 # thus there is no r such that r^2 = 6 mod 35 gap> Jacobi( 3, 35 ); 1 # even though there is no r with r^2 = 3 mod 35
Legendre( n, m ) F
Legendre returns the value of the Legendre symbol of the integer n
modulo the positive integer m.
The value of the Legendre symbol L(n /m ) is 1 if n is a quadratic residue modulo m, i.e., if there exists an integer r such that r2 º n mod m and -1 otherwise.
If a root of n exists it can be found by RootMod (see RootMod).
While the value of the Legendre symbol usually is only defined for m a prime, we have extended the definition to include composite moduli too. The Jacobi symbol (see Jacobi) is another generalization of the Legendre symbol for composite moduli that is much cheaper to compute, because it does not need the factorization of m (see FactorsInt).
A description of the Jacobi symbol, the Legendre symbol, and related topics can be found in Baker84.
gap> Legendre( 5, 11 ); 1 # 4^2 = 5 mod 11 gap> Legendre( 6, 11 ); -1 # thus there is no r such that r^2 = 6 mod 11 gap> Legendre( 3, 35 ); -1 # thus there is no r such that r^2 = 3 mod 35
RootMod( n[, k], m ) F
RootMod computes a kth root of the integer n modulo the positive
integer m, i.e., a r such that rk º n mod m .
If no such root exists RootMod returns fail.
If only the arguments n and m are given,
the default value for k is 2.
In the current implementation k must be a prime.
A square root of n exists only if Legendre(n,m) = 1
(see Legendre).
If m has r different prime factors then there are 2r different
roots of n mod m. It is unspecified which one RootMod returns.
You can, however, use RootsMod (see RootsMod) to compute the full set
of roots.
RootMod is efficient even for large values of m, in fact the most
time is usually spent factoring m (see FactorsInt).
gap> RootMod( 64, 1009 ); 1001 # note 'RootMod' does not return 8 in this case but -8 gap> RootMod( 64, 3, 1009 ); 518 gap> RootMod( 64, 5, 1009 ); 656 gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ), > x -> x mod 1009 ); [ 1001, 8 ] # set of all square roots of 64 mod 1009
RootsMod( n[, k], m ) F
RootsMod computes the set of kth roots of the integer n
modulo the positive integer m, i.e., a r such that
rk º n mod m .
If only the arguments n and m are given,
the default value for k is 2.
In the current implementation k must be a prime.
gap> RootsMod( 1, 7*31 ); # the same as `RootsUnityMod( 7*31 )' [ 1, 92, 125, 216 ] gap> RootsMod( 7, 7*31 ); [ 21, 196 ] gap> RootsMod( 5, 7*31 ); [ ] gap> RootsMod( 1, 5, 7*31 ); [ 1, 8, 64, 78, 190 ]
RootsUnityMod( [k, ] m ) F
RootsUnityMod returns the set of k-th roots of unity modulo the
positive integer m, i.e.,
the list of all solutions r of rk º n mod m .
If only the argument m is given, the default value for k is 2.
In general there are k n such roots if the modulus m has n different prime factors p such that p º 1 mod k . If k 2 divides m then there are k n+1 such roots; and especially if k = 2 and 8 divides m there are 2n+2 such roots.
In the current implementation k must be a prime.
gap> RootsUnityMod( 7*31 ); RootsUnityMod( 3, 7*31 ); [ 1, 92, 125, 216 ] [ 1, 25, 32, 36, 67, 149, 156, 191, 211 ] gap> RootsUnityMod( 5, 7*31 ); [ 1, 8, 64, 78, 190 ] gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ), > x -> x mod 1009 ); [ 1001, 8 ] # set of all square roots of 64 mod 1009
Sigma( n ) F
Sigma returns the sum of the positive divisors of the integer n.
Sigma is a multiplicative arithmetic function, i.e., if n and m are
relatively prime we have s(n m) = s(n ) s(m).
Together with the formula s(pe) = (pe+1-1) / (p-1) this allows us to compute s(n ).
Integers n for which s(n )=2 n are called perfect. Even perfect integers are exactly of the form 2n -1(2n -1) where 2n -1 is prime. Primes of the form 2n -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 BC89 show that any such integer must have at least 300 decimal digits.
Sigma usually spends most of its time factoring n (see FactorsInt).
gap> Sigma( 0 ); Error, Sigma: <n> must not be 0 called from ... 4 lines omitted here ... brk> quit;
gap> Sigma( 1 ); Sigma( 1009 ); Sigma( 8128 ) = 2*8128; 1 1010 # thus 1009 is a prime true # thus 8128 is a perfect number
Tau( n ) F
Tau returns the number of the positive divisors of the integer n.
Tau is a multiplicative arithmetic function, i.e., if n and m are
relative prime we have t(n m) = t(n ) t(m).
Together with the formula t(pe) = e+1 this allows us to compute
t(n ).
Tau usually spends most of its time factoring n (see FactorsInt).
gap> Tau( 0 ); Error, Tau: <n> must not be 0 called from ... 4 lines omitted here ... brk> quit;
gap> Tau( 1 ); Tau( 1013 ); Tau( 8128 ); Tau( 36 ); 1 2 # thus 1013 is a prime 14 9 # the result is odd if and only if the argument is a perfect square
MoebiusMu( n ) F
MoebiusMu computes the value of Moebius inversion function for the
integer n. This is 0 for integers which are not squarefree, i.e.,
which are divided by a square r2. Otherwise it is 1 if n has a even
number and -1 if n has an odd number of prime factors.
The importance of m stems from the so called inversion formula. Suppose f(n ) is a multiplicative arithmetic function defined on the positive integers and let g(n )=åd | n f(d). Then f(n )=åd | n m(d) g(n /d). As a special case we have f(n ) = åd | n m(d) n /d since n = åd | n f(d) (see Phi).
MoebiusMu usually spends all of its time factoring n (see
FactorsInt).
gap> MoebiusMu( 60 ); MoebiusMu( 61 ); MoebiusMu( 62 ); 0 -1 1
TwoSquares( n ) F
TwoSquares returns a list of two integers x £ y such that the sum of
the squares of x and y is equal to the nonnegative integer n, i.e.,
n = x2+y2. If no such representation exists TwoSquares will return
fail. TwoSquares will return a representation for which the gcd of
x and y is as small as possible. It is not specified which
representation TwoSquares returns, if there is more than one.
Let a be the product of all maximal powers of primes of the form 4k+3 dividing n. A representation of n as a sum of two squares exists if and only if a is a perfect square. Let b be the maximal power of 2 dividing n or its half, whichever is a perfect square. Then the minimal possible gcd of x and y is the square root c of a b. The number of different minimal representation with x £ y is 2l-1, where l is the number of different prime factors of the form 4k+1 of n.
The algorithm first finds a square root r of -1 modulo n / (a b), which must exist, and applies the Euclidean algorithm to r and n. The first residues in the sequence that are smaller than Ö{n /(a b)} times c are a possible pair x and y.
Better descriptions of the algorithm and related topics can be found in Wagon90 and Zagier90.
gap> TwoSquares( 5 ); TwoSquares( 11 ); [ 1, 2 ] fail # no representation exists gap> TwoSquares( 16 ); TwoSquares( 45 ); [ 0, 4 ] [ 3, 6 ] # 3 is the minimal possible gcd because 9 divides 45 gap> TwoSquares( 125 ); TwoSquares( 13*17 ); [ 2, 11 ] # not [ 5, 10 ] because this has not minimal gcd [ 5, 14 ] # [10,11] would be the other possible representation gap> TwoSquares( 848654483879497562821 ); #I beyond the guaranteed bound of the probabilistic primality test [ 6305894639, 28440994650 ] # 848654483879497562821 is prime
[Top] [Up] [Previous] [Next] [Index]
GAP 4 manual
May 2002