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

Param n

integer to test

IsComposite(n)

test for a composite number

Param n

positive integer

IsCoprime(m, n)

test if integers are coprime

Param m

positive integer

Param n

positive integer

Param list

list of positive integers

IsSquareFree(n)

test for a square-free number

Param n

positive integer

IsPrimePower(n)

test for a power of a prime number

Param n

integer to test

NextPrime(i)

generate a prime following a number

Param i

integer value

IsTwinPrime(n)

test for a twin prime

Param n

positive integer

IsIrregularPrime(n)

test for an irregular prime

Param n

positive integer

IsCarmichaelNumber(n)

test for a Carmichael number

Param n

positive integer

Factors(x)

factorization

Param x

integer or univariate polynomial

IsAmicablePair(m, n)

test for a pair of amicable numbers

Param m

positive integer

Param n

positive integer

Factor(x)

factorization, in pretty form

Param x

integer or univariate polynomial

Divisors(n)

number of divisors

Param n

positive integer

DivisorsSum(n)

the sum of divisors

Param n

positive integer

ProperDivisors(n)

the number of proper divisors

Param n

positive integer

ProperDivisorsSum(n)

the sum of proper divisors

Param n

positive integer

Moebius(n)

the Moebius function

Param n

positive integer

CatalanNumber(n)

return the n-th Catalan Number

Param n

positive integer

FermatNumber(n)

return the n-th Fermat Number

Param n

positive integer

HarmonicNumber(n)

return the n-th Harmonic Number

Param n

positive integer

Param r

positive integer

StirlingNumber1(n, m)

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

Param n

positive integers

Param m

positive integers

StirlingNumber1(n, m)

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

Param n

positive integer

Param m

positive integer

DivisorsList(n)

the list of divisors

Param n

positive integer

SquareFreeDivisorsList(n)

the list of square-free divisors

Param n

positive integer

MoebiusDivisorsList(n)

the list of divisors and Moebius values

Param n

positive integer

SumForDivisors(var, n, expr)

loop over divisors

Param var

atom, variable name

Param n

positive integer

Param expr

expression depending on var

RamanujanSum(k, n)

compute the Ramanujan’s sum

Param k

positive integer

Param 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

Param n

number or polynomial to expand

Param p

base to expand in

IsQuadraticResidue(m, n)

functions related to finite groups

Param m

integer

Param n

odd positive integer

GaussianFactors(z)

factorization in Gaussian integers

Param z

Gaussian integer

GaussianNorm(z)

norm of a Gaussian integer

Param z

Gaussian integer

IsGaussianUnit(z)

test for a Gaussian unit

Param z

a Gaussian integer

IsGaussianPrime(z)

test for a Gaussian prime

Param z

a complex or real number

GaussianGcd(z, w)

greatest common divisor in Gaussian integers

Param z

Gaussian integer

Param w

Gaussian integer