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(n)

test for a prime number

Parameters:n – integer to test

IsComposite(n)

test for a composite number

Parameters:n – positive integer

IsCoprime(m, n)

test if integers are coprime

Parameters:

• m – positive integer
• n – positive integer
• list – list of positive integers

IsSquareFree(n)

test for a square-free number

Parameters:n – positive integer

IsPrimePower(n)

test for a power of a prime number

Parameters:n – integer to test

NextPrime(i)

generate a prime following a number

Parameters:i – integer value

IsTwinPrime(n)

test for a twin prime

Parameters:n – positive integer

IsIrregularPrime(n)

test for an irregular prime

Parameters:n – positive integer

IsCarmichaelNumber(n)

test for a Carmichael number

Parameters:n – positive integer

Factors(x)

factorization

Parameters:x – integer or univariate polynomial

IsAmicablePair(m, n)

test for a pair of amicable numbers

Parameters:

• m – positive integer
• n – positive integer

Factor(x)

factorization, in pretty form

Parameters:x – integer or univariate polynomial

Divisors(n)

number of divisors

Parameters:n – positive integer

DivisorsSum(n)

the sum of divisors

Parameters:n – positive integer

ProperDivisors(n)

the number of proper divisors

Parameters:n – positive integer

ProperDivisorsSum(n)

the sum of proper divisors

Parameters:n – positive integer

Moebius(n)

the Moebius function

Parameters:n – positive integer

CatalanNumber(n)

return the n-th Catalan Number

Parameters:n – positive integer

FermatNumber(n)

return the n-th Fermat Number

Parameters:n – positive integer

HarmonicNumber(n)

return the n-th Harmonic Number

Parameters:

• n – positive integer
• r – positive integer

StirlingNumber1(n, m)

return the n,m-th Stirling Number of the first kind

Parameters:

• n – positive integers
• m – positive integers

StirlingNumber1(n, m)

return the n,m-th Stirling Number of the second kind

Parameters:

• n – positive integer
• m – positive integer

DivisorsList(n)

the list of divisors

Parameters:n – positive integer

SquareFreeDivisorsList(n)

the list of square-free divisors

Parameters:n – positive integer

MoebiusDivisorsList(n)

the list of divisors and Moebius values

Parameters:n – positive integer

SumForDivisors(var, n, expr)

loop over divisors

Parameters:

• var – atom, variable name
• n – positive integer
• expr – expression depending on var

RamanujanSum(k, n)

compute the Ramanujan’s sum

Parameters:

• k – positive integer
• n – positive integer

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

\[\sum_{l=1}^k\frac{\exp(2ln\pi\imath)}{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, <i>Introduction to Analytic Theory</i> (Springer-Verlag), Theorem 8.6.

Todo

check the definition

PAdicExpand(n, p)

p-adic expansion

Parameters:

• n – number or polynomial to expand
• p – base to expand in

IsQuadraticResidue(m, n)

functions related to finite groups

Parameters:

• m – integer
• n – odd positive integer

GaussianFactors(z)

factorization in Gaussian integers

Parameters:z – Gaussian integer

GaussianNorm(z)

norm of a Gaussian integer

Parameters:z – Gaussian integer

IsGaussianUnit(z)

test for a Gaussian unit

Parameters:z – a Gaussian integer

IsGaussianPrime(z)

test for a Gaussian prime

Parameters:z – a complex or real number

GaussianGcd(z, w)

greatest common divisor in Gaussian integers

Parameters:

• z – Gaussian integer
• w – Gaussian integer