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