IsPrime, IsSmallPrime , IsComposite , IsCoprime , IsSquareFree , IsPrimePower , NextPrime , IsTwinPrime , IsIrregularPrime , IsCarmichaelNumber , Factors , IsAmicablePair , Factor , Divisors , DivisorsSum , ProperDivisors , ProperDivisorsSum , Moebius , CatalanNumber , FermatNumber , HarmonicNumber , StirlingNumber1 , StirlingNumber2 , DivisorsList , SquareFreeDivisorsList , MoebiusDivisorsList , SumForDivisors , RamanujanSum , Cyclotomic , PAdicExpand , IsQuadraticResidue, LegendreSymbol, JacobiSymbol , GaussianFactors , GaussianNorm , IsGaussianUnit , IsGaussianPrime , GaussianGcd .

Number theory

This chapter describes functions that are of interest in number theory. These functions typically operate on integers. Some of these functions work quite slowly.

IsPrime, IsSmallPrime test for a prime number
IsComposite test for a composite number
IsCoprime test if integers are coprime
IsSquareFree test for a square-free number
IsPrimePower test for a power of a prime number
NextPrime generate a prime following a number
IsTwinPrime test for a twin prime
IsIrregularPrime test for an irregular prime
IsCarmichaelNumber test for a Carmichael number
Factors factorization
IsAmicablePair test for a pair of amicable numbers
Factor factorization, in pretty form
Divisors number of divisors
DivisorsSum the sum of divisors
ProperDivisors the number of proper divisors
ProperDivisorsSum the sum of proper divisors
Moebius the Moebius function
CatalanNumber return the nth Catalan Number
FermatNumber return the nth Fermat Number
HarmonicNumber return the nth Harmonic Number
StirlingNumber1 return the n,mth Stirling Number of the first kind
StirlingNumber2 return the n,mth Stirling Number of the second kind
DivisorsList the list of divisors
SquareFreeDivisorsList the list of square-free divisors
MoebiusDivisorsList the list of divisors and Moebius values
SumForDivisors loop over divisors
RamanujanSum compute the "Ramanujan sum"
Cyclotomic construct the cyclotomic polynomial
PAdicExpand p-adic expansion
IsQuadraticResidue, LegendreSymbol, JacobiSymbol functions related to finite groups
GaussianFactors factorization in Gaussian integers
GaussianNorm norm of a Gaussian integer
IsGaussianUnit test for a Gaussian unit
IsGaussianPrime test for a Gaussian prime
GaussianGcd greatest common divisor in Gaussian integers


IsPrime, IsSmallPrime -- test for a prime number

Standard library
Calling format:
IsPrime(n)
IsSmallPrime(n)

Parameters:
n -- integer to test

Description:
The commands checks whether n, which should be a positive integer, is a prime number. A number n is a prime number if it is only divisible by 1 and itself. As a special case, 1 is not considered a prime number. The first prime numbers are 2, 3, 5, ...

The function IsShortPrime only works for numbers n<=65537 but it is very fast.

The function IsPrime operates on all numbers and uses different algorithms depending on the magnitude of the number n. For small numbers n<=65537, a constant-time table lookup is performed. (The function IsShortPrime is used for that.) For numbers n between 65537 and 34155071728321, the function uses the Rabin-Miller test together with table lookups to guarantee correct results.

For even larger numbers a version of the probabilistic Rabin-Miller test is executed. The test can sometimes mistakenly mark a number as prime while it is in fact composite, but a prime number will never be mistakenly declared composite. The parameters of the test are such that the probability for a false result is less than 10^(-24).

Examples:
In> IsPrime(1)
Out> False;
In> IsPrime(2)
Out> True;
In> IsPrime(10)
Out> False;
In> IsPrime(23)
Out> True;
In> Select("IsPrime", 1 .. 100)
Out> {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
  53,59,61,67,71,73,79,83,89,97};

See also:
IsPrimePower , Factors .


IsComposite -- test for a composite number

Standard library
Calling format:
IsComposite(n)

Parameters:
n -- positive integer

Description:
This function is the logical negation of IsPrime, except for the number 1, which is neither prime nor composite.

Examples:
In> IsComposite(1)
Out> False;
In> IsComposite(7)
Out> False;
In> IsComposite(8)
Out> True;
In> Select(IsComposite,1 .. 20)
Out> {4,6,8,9,10,12,14,15,16,18,20};

See also:
IsPrime .


IsCoprime -- test if integers are coprime

Standard library
Calling format:
IsCoprime(m,n)
IsCoprime(list)
Parameters:
m,n -- positive integers

list -- list of positive integers

Description:
This function returns True if the given pair or list of integers are coprime, also called relatively prime. A pair or list of numbers are coprime if they share no common factors.

Examples:
In> IsCoprime({3,4,5,8})
Out> False;
In> IsCoprime(15,17)
Out> True;

See also:
Prime .


IsSquareFree -- test for a square-free number

Standard library
Calling format:
IsSquareFree(n)

Parameters:
n -- positive integer

Description:
This function uses the Moebius function to tell if the given number is square-free, which means it has distinct prime factors. If Moebius(n)!=0, then n is square free. All prime numbers are trivially square-free.

Examples:
In> IsSquareFree(37)
Out> True;
In> IsSquareFree(4)
Out> False;
In> IsSquareFree(16)
Out> False;
In> IsSquareFree(18)
Out> False;

See also:
Moebius , SquareFreeDivisorsList .


IsPrimePower -- test for a power of a prime number

Standard library
Calling format:
IsPrimePower(n)

Parameters:
n -- integer to test

Description:
This command tests whether "n", which should be a positive integer, is a prime power, that is whether it is of the form p^m, with "p" prime and "m" an integer.

This function does not try to decompose the number n into factors. Instead we check for all prime numbers r=2, 3, ... that the r-th root of n is an integer, and we find such r and m that n=m^r, we check that m is a prime. If it is not a prime, we execute the same function call on m.

Examples:
In> IsPrimePower(9)
Out> True;
In> IsPrimePower(10)
Out> False;
In> Select("IsPrimePower", 1 .. 50)
Out> {2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,
  29,31,32,37,41,43,47,49};

See also:
IsPrime , Factors .


NextPrime -- generate a prime following a number

Standard library
Calling format:
NextPrime(i)

Parameters:
i -- integer value

Description:
The function finds the smallest prime number that is greater than the given integer value.

The routine generates "candidate numbers" using the formula n+2*Mod(-n,3) where n is an odd number (this generates the sequence 5, 7, 11, 13, 17, 19, ...) and IsPrime() to test whether the next candidate number is in fact prime.

Example:
In> NextPrime(5)
Out> 7;

See also:
IsPrime .


IsTwinPrime -- test for a twin prime

Standard library
Calling format:
IsTwinPrime(n)
Parameters:
n -- positive integer

Description:
This function returns True if n is a twin prime. By definition, a twin prime is a prime number n such that n+2 is also a prime number.

Examples:
In> IsTwinPrime(101)
Out> True;
In> IsTwinPrime(7)
Out> False;
In> Select(IsTwinPrime, 1 .. 100)
Out> {3,5,11,17,29,41,59,71};

See also:
IsPrime .


IsIrregularPrime -- test for an irregular prime

Standard library
Calling format:
IsIrregularPrime(n)

Parameters:
n -- positive integer

Description:
This function returns True if n is an irregular prime. A prime number n is irregular if and only if n divides the numerator of a Bernoulli number B[2*i], where 2*i+1<n. Small irregular primes are quite rare; the only irregular primes under 100 are 37, 59 and 67. Asymptotically, roughly 40% of primes are irregular.

Examples:
In> IsIrregularPrime(5)
Out> False;
In> Select(IsIrregularPrime,1 .. 100)
Out> {37,59,67};

See also:
IsPrime .


IsCarmichaelNumber -- test for a Carmichael number

Standard library
Calling format:
IsCarmichaelNumber(n)

Parameters:
n -- positive integer

Description:
This function returns True if n is a Carmichael number, also called an absolute pseudoprime. They have the property that b^(n-1)%n==1 for all b satisfying Gcd(b,n)==1. These numbers cannot be proved composite by Fermat's little theorem. Because the previous property is extremely slow to test, the following equivalent property is tested by Yacas: for all prime factors p[i] of n, (n-1)%(p[i]-1)==0 and n must be square free. Also, Carmichael numbers must be odd and have at least three prime factors. Although these numbers are rare (there are only 43 such numbers between 1 and 10^6), it has recently been proven that there are infinitely many of them.

Examples:
In> IsCarmichaelNumber(561)
Out> True;
In> Time(Select(IsCarmichaelNumber,1 .. 10000))
504.19 seconds taken
Out> {561,1105,1729,2465,2821,6601,8911};

See also:
IsSquareFree , IsComposite .


Factors -- factorization

Standard library
Calling format:
Factors(x)

Parameters:
x -- integer or univariate polynomial

Description:
This function decomposes the integer number x into a product of numbers. Alternatively, if x is a univariate polynomial, it is decomposed in irreducible polynomials.

The factorization is returned as a list of pairs. The first member of each pair is the factor, while the second member denotes the power to which this factor should be raised. So the factorization x=p1^n1*...*p9^n9 is returned as {{p1,n1}, ..., {p9,n9}}.

Examples:
In> Factors(24);
Out> {{2,3},{3,1}};
In> Factors(2*x^3 + 3*x^2 - 1);
Out> {{2,1},{x+1,2},{x-1/2,1}};

See also:
Factor , IsPrime , GaussianFactors .


IsAmicablePair -- test for a pair of amicable numbers

Standard library
Calling format:
IsAmicablePair(m,n)

Parameters:
m, n -- positive integers

Description:
This function tests if a pair of numbers are amicable. A pair of numbers m, n has this property if the sum of the proper divisors of m is n and the sum of the proper divisors of n is m.

Examples:
In> IsAmicablePair(200958394875, 209194708485 )
Out> True;
In> IsAmicablePair(220, 284)
Out> True;

See also:
ProperDivisorsSum .


Factor -- factorization, in pretty form

Standard library
Calling format:
Factor(x)

Parameters:
x -- integer or univariate polynomial

Description:
This function factorizes "x", similarly to Factors, but it shows the result in a nicer human readable format.

Examples:
In> PrettyForm(Factor(24));

 3
2  * 3

Out> True;
In> PrettyForm(Factor(2*x^3 + 3*x^2 - 1));

             2   /     1 \
2 * ( x + 1 )  * | x - - |
                 \     2 /

Out> True;

See also:
Factors , IsPrime , PrettyForm .


Divisors -- number of divisors

Standard library
Calling format:
Divisors(n)
Parameters:
n -- positive integer

Description:
Divisors returns the number of positive divisors of a number. A number is prime if and only if it has two divisors, 1 and itself.

Examples:
In> Divisors(180)
Out> 18;
In> Divisors(37)
Out> 2;

See also:
DivisorsSum , ProperDivisors , ProperDivisorsSum , Moebius .


DivisorsSum -- the sum of divisors

Standard library
Calling format:
DivisorsSum(n)
Parameters:
n -- positive integer

Description:
DivisorsSum returns the sum all numbers that divide it. A number n is prime if and only if the sum of its divisors are n+1.

Examples:
In> DivisorsSum(180)
Out> 546;
In> DivisorsSum(37)
Out> 38;

See also:
DivisorsSum , ProperDivisors , ProperDivisorsSum , Moebius .


ProperDivisors -- the number of proper divisors

Standard library
Calling format:
ProperDivisors(n)
Parameters:
n -- positive integer

Description:
ProperDivisors returns the number of proper divisors, i.e Divisors(n)-1, since n is not counted. An integer n is prime if and only if it has 1 proper divisor.

Examples:
In> ProperDivisors(180)
Out> 17;
In> ProperDivisors(37)
Out> 1;

See also:
DivisorsSum , ProperDivisors , ProperDivisorsSum , Moebius .


ProperDivisorsSum -- the sum of proper divisors

Standard library
Calling format:
ProperDivisorsSum(n)
Parameters:
n -- positive integer

Description:
ProperDivisorsSum returns the sum of proper divisors, i.e. ProperDivisors(n)-n, since n is not counted. n is prime if and only if ProperDivisorsSum(n)==1.

Examples:
In> ProperDivisorsSum(180)
Out> 366;
In> ProperDivisorsSum(37)
Out> 1;

See also:
DivisorsSum , ProperDivisors , ProperDivisorsSum , Moebius .


Moebius -- the Moebius function

Standard library
Calling format:
Moebius(n)
Parameters:
n -- positive integer

Description:
The Moebius function is 0 when a prime factor is repeated (which means it is not square-free) and is (-1)^r if n has r distinct factors. Also, Moebius(1)==1.

Examples:
In> Moebius(10)
Out> 1;
In> Moebius(11)
Out> -1;
In> Moebius(12)
Out> 0;
In> Moebius(13)
Out> -1;

See also:
DivisorsSum , ProperDivisors , ProperDivisorsSum , MoebiusDivisorsList .


CatalanNumber -- return the nth Catalan Number

Standard library
Calling format:
CatalanNumber(n)
Parameters:
n -- positive integer

Description:
This function returns the n-th Catalan number, defined as Bin(2*n,n)/(n+1).

Examples:
In> CatalanNumber(10)
Out> 16796;
In> CatalanNumber(5)
Out> 42;

See also:
Bin .


FermatNumber -- return the nth Fermat Number

Standard library
Calling format:
FermatNumber(n)
Parameters:
n -- positive integer

Description:
This function returns the n-th Fermat number, which is defined as 2^2^n+1.

Examples:
In> FermatNumber(7)
Out> 340282366920938463463374607431768211457;

See also:
Factor .


HarmonicNumber -- return the nth Harmonic Number

Standard library
Calling format:
HarmonicNumber(n)
HarmonicNumber(n,r)
Parameters:
n, r -- positive integers

Description:
This function returns the n-th Harmonic number, which is defined as Sum(k,1,n,1/k). If given a second argument, the Harmonic number of order r is returned, which is defined as Sum(k,1,n,k^(-r)).

Examples:
In> HarmonicNumber(10)
Out> 7381/2520;
In> HarmonicNumber(15)
Out> 1195757/360360;
In> HarmonicNumber(1)
Out> 1;
In> HarmonicNumber(4,3)
Out> 2035/1728;

See also:
Sum .


StirlingNumber1 -- return the n,mth Stirling Number of the first kind

Standard library
Calling format:
StirlingNumber1(n,m)
Parameters:
n, m -- positive integers

Description:
This function returns the signed Stirling Number of the first kind. All Stirling Numbers are integers. If m>n, then StirlingNumber1 returns 0.

Examples:
In> StirlingNumber1(10,5)
Out> -269325;
In> StirlingNumber1(3,6)
Out> 0;

See also:
StirlingNumber2 .


StirlingNumber2 -- return the n,mth Stirling Number of the second kind

Standard library
Calling format:
StirlingNumber1(n,m)
Parameters:
n, m -- positive integers

Description:
This function returns the Stirling Number of the second kind. All Stirling Numbers are positive integers. If m>n, then StirlingNumber2 returns 0.

Examples:
In> StirlingNumber2(3,6)
Out> 0;
In> StirlingNumber2(10,4)
Out> 34105;

See also:
StirlingNumber1 .


DivisorsList -- the list of divisors

Standard library
Calling format:
DivisorsList(n)
Parameters:
n -- positive integer

Description:
DivisorsList creates a list of the divisors of n. This is useful for loops like

ForEach(d,DivisorsList(n))

Examples:
In> DivisorsList(18)
Out> {1,2,3,6,9,18};

See also:
DivisorsSum .


SquareFreeDivisorsList -- the list of square-free divisors

Standard library
Calling format:
SquareFreeDivisorsList(n)
Parameters:
n -- positive integer

Description:
SquareFreeDivisorsList creates a list of the square-free divisors of n. Square-free numbers are numbers that have only simple prime factors (no prime powers). For example, 18=2*3*3 is not square-free because it contains a square of 3 as a factor.

Examples:
In> SquareFreeDivisorsList(18)
Out> {1,2,3,6};

See also:
DivisorsList .


MoebiusDivisorsList -- the list of divisors and Moebius values

Standard library
Calling format:
MoebiusDivisorsList(n)
Parameters:
n -- positive integer

Description:
Returns a list of pairs of the form {d,m}, where d runs through the squarefree divisors of n and m=Moebius(d). This is more efficient than making a list of all square-free divisors of n and then computing Moebius on each of them. It is useful for computing the cyclotomic polynomials. It can be useful in other computations based on the Moebius inversion formula.

Examples:
In> MoebiusDivisorsList(18)
Out> {{1,1},{2,-1},{3,-1},{6,1}};

See also:
DivisorsList , Moebius .


SumForDivisors -- loop over divisors

Standard library
Calling format:
SumForDivisors(var,n,expr)
Parameters:
var -- atom, variable name

n -- positive integer

expr -- expression depending on var

Description:
This function performs the sum of the values of the expression expr while the variable var runs through the divisors of n. For example, SumForDivisors(d, 10, d^2) sums d^2 where d runs through the divisors of 10. This kind of computation is frequently used in number theory.

See also:
DivisorsList .


RamanujanSum -- compute the "Ramanujan sum"

Standard library
Calling format:
RamanujanSum(k,n)

Parameters:
k, n -- positive integers

Description:
This function computes the Ramanujan sum, i.e. the sum of the n-th powers of the k-th primitive roots of the unit:

Sum(l,1,k,Exp(2*Pi*I*(l*n)/k))

where l runs thought the integers between 1 and k-1 that are coprime to l.

The computation is done by using the formula in T. M. Apostol, Introduction to Analytic Theory (Springer-Verlag), Theorem 8.6.


Cyclotomic -- construct the cyclotomic polynomial

Standard library
Calling format:
Cyclotomic(n,x)

Parameters:
n -- positive integer

x -- variable

Description:
Returns the cyclotomic polynomial in the variable x (which is the minimal polynomial of the n-th primitive roots of the unit, over the field of rational numbers).

For n even, we write n=m*k, where k is a power of 2 and m is odd, and reduce it to the case of even m since

Cyclotomic(n,x)=Cyclotomic(m,-x^(k/2)).

If m=1, n is a power of 2, and Cyclotomic(n,x)=x^k+1.

For n odd, the algorithm is based on the formula

Cyclotomic(n,x):=Prod((x^(n/d)-1)^mu(d)),

where d runs through the divisors of n. In order to compute this in a efficient way, we use the function MoebiusDivisorsList. Then we compute in poly1 the product of x^(n/d)-1 with mu(d)=1 , and in poly2 the product of these polynomials with mu(d)= -1. Finally we compute the quotient poly1/poly2.

See also:
RamanujanSum .


PAdicExpand -- p-adic expansion

Standard library
Calling format:
PAdicExpand(n, p)

Parameters:
n -- number or polynomial to expand

p -- base to expand in

Description:
This command computes the p-adic expansion of n. In other words, n is expanded in powers of p. The argument n can be either an integer or a univariate polynomial. The base p should be of the same type.

Examples:
In> PrettyForm(PAdicExpand(1234, 10));

               2     3
3 * 10 + 2 * 10  + 10  + 4

Out> True;
In> PrettyForm(PAdicExpand(x^3, x-1));

                             2            3
3 * ( x - 1 ) + 3 * ( x - 1 )  + ( x - 1 )  + 1

Out> True;

See also:
Mod , ContFrac , FromBase , ToBase .


IsQuadraticResidue, LegendreSymbol, JacobiSymbol -- functions related to finite groups

Standard library
Calling format:
IsQuadraticResidue(m,n)
LegendreSymbol(m,n)
JacobiSymbol(m,n)

Parameters:
m, n -- integers, n must be odd and positive

Description:
A number m is a "quadratic residue modulo n" if there exists a number k such that k^2:=Mod(m,n).

The Legendre symbol (m/ n) is defined as +1 if m is a quadratic residue modulo n and -1 if it is a non-residue. The Legendre symbol is equal to 0 if m/n is an integer.

The Jacobi symbol [m/n;] is defined as the product of the Legendre symbols of the prime factors f[i] of n=f[1]^p[1]*...*f[s]^p[s],

[m/n;]:=[m/f[1];]^p[1]*...*[m/f[s];]^p[s].

(Here we used the same notation [a/b;] for the Legendre and the Jacobi symbols; this is confusing but seems to be the current practice.) The Jacobi symbol is equal to 0 if m, n are not mutually prime (have a common factor). The Jacobi symbol and the Legendre symbol have values +1, -1 or 0. If n is prime, then the Jacobi symbol is the same as the Legendre symbol.

The Jacobi symbol can be efficiently computed without knowing the full factorization of the number n.

Examples:
In> IsQuadraticResidue(9,13)
Out> True;
In> LegendreSymbol(15,23)
Out> -1;
In> JacobiSymbol(7,15)
Out> -1;

See also:
Gcd .


GaussianFactors -- factorization in Gaussian integers

Standard library
Calling format:
GaussianFactors(z)

Parameters:
z -- Gaussian integer

Description:
This function decomposes a Gaussian integer number z into a product of Gaussian prime factors. A Gaussian integer is a complex number with integer real and imaginary parts. A Gaussian integer z can be decomposed into Gaussian primes essentially in a unique way (up to Gaussian units and associated prime factors), i.e. one can write z as

z=u*p[1]^n[1]*...*p[s]^n[s],

where u is a Gaussian unit and p[1], p[2], ..., p[s] are Gaussian primes.

The factorization is returned as a list of pairs. The first member of each pair is the factor (a Gaussian integer) and the second member denotes the power to which this factor should be raised. So the factorization is returned as a list, e.g. {{p1,n1}, {p2,n2}, ...}.

Examples:
In> GaussianFactors(5)
Out> {{Complex(2,1),1},{Complex(2,-1),1}};
In> GaussianFactors(3+I)
Out> {{Complex(1,1),1},{Complex(2,-1),1}};

See also:
Factors , IsGaussianPrime , IsGaussianUnit .


GaussianNorm -- norm of a Gaussian integer

Standard library
Calling format:
GaussianNorm(z)

Parameters:
z -- Gaussian integer

Description:
This function returns the norm of a Gaussian integer z=a+b*I, defined as a^2+b^2.

Examples:
In> GaussianNorm(2+I)
Out> 5; 

See also:
IsGaussianInteger .


IsGaussianUnit -- test for a Gaussian unit

Standard library
Calling format:
IsGaussianUnit(z)
Parameters:
z -- a Gaussian integer

Description:
This function returns True if the argument is a unit in the Gaussian integers and False otherwise. A unit in a ring is an element that divides any other element.

There are four "units" in the ring of Gaussian integers, which are 1, -1, I, and -I.

Examples:
In> IsGaussianInteger(I)
Out> True;
In> IsGaussianUnit(5+6*I)
Out> False;

See also:
IsGaussianInteger , IsGaussianPrime , GaussianNorm .


IsGaussianPrime -- test for a Gaussian prime

Standard library
Calling format:
IsGaussianPrime(z)
Parameters:
z -- a complex or real number

Description:
This function returns True if the argument is a Gaussian prime and False otherwise.

A prime element x of a ring is divisible only by the units of the ring and by associates of x. ("Associates" of x are elements of the form x*u where u is a unit of the ring).

Gaussian primes are Gaussian integers z=a+b*I that satisfy one of the following properties:

Examples:
In> IsGaussianPrime(13)
Out> False;
In> IsGaussianPrime(2+2*I)
Out> False;
In> IsGaussianPrime(2+3*I)
Out> True;
In> IsGaussianPrime(3)
Out> True;

See also:
IsGaussianInteger , GaussianFactors .


GaussianGcd -- greatest common divisor in Gaussian integers

Standard library
Calling format:
GaussianGcd(z,w)

Parameters:
z, w -- Gaussian integers

Description:
This function returns the greatest common divisor, in the ring of Gaussian integers, computed using Euclid's algorithm. Note that in the Gaussian integers, the greatest common divisor is only defined up to a Gaussian unit factor.

Examples:
In> GaussianGcd(2+I,5)
Out> Complex(2,1);
The GCD of two mutually prime Gaussian integers might come out to be equal to some Gaussian unit instead of 1:
In> GaussianGcd(2+I,3+I)
Out> -1;

See also:
Gcd , Lcm , IsGaussianUnit .