Integer and Number Theoretic Functions

Mod[k,n]k modulo n (remainder from dividing k by n)
Quotient[m,n]the quotient of m and n (truncation of )
QuotientRemainder[m,n]a list of the quotient and the remainder
Divisible[m,n]test whether m is divisible by n
CoprimeQ[n1,n2,]test whether the are pairwise relatively prime
GCD[n1,n2,]the greatest common divisor of , ,
LCM[n1,n2,]the least common multiple of , ,
KroneckerDelta[n1,n2,]the Kronecker delta equal to 1 if all the are equal, and 0 otherwise
IntegerDigits[n,b]the digits of n in base b
IntegerExponent[n,b]the highest power of b that divides n

Some integer functions.

The remainder on dividing 17 by 3.
In[1]:=
Click for copyable input
Out[1]=
The integer part of 17/3.
In[2]:=
Click for copyable input
Out[2]=
Mod also works with real numbers.
In[3]:=
Click for copyable input
Out[3]=
The result from Mod always has the same sign as the second argument.
In[4]:=
Click for copyable input
Out[4]=

For any integers a and b, it is always true that b*Quotient[a,b]+Mod[a,b] is equal to .

Mod[k,n]result in the range 0 to
Mod[k,n,1]result in the range 1 to n
Mod[k,n,-n/2]result in the range to
Mod[k,n,d]result in the range d to

Integer remainders with offsets.

Particularly when you are using Mod to get indices for parts of objects, you will often find it convenient to specify an offset.

This effectively extracts the 18^(th) part of the list, with the list treated cyclically.
In[5]:=
Click for copyable input
Out[5]=

The greatest common divisor function GCD[n1,n2,] gives the largest integer that divides all the exactly. When you enter a ratio of two integers, the Wolfram Language effectively uses GCD to cancel out common factors and give a rational number in lowest terms.

The least common multiple function LCM[n1,n2,] gives the smallest integer that contains all the factors of each of the .

The largest integer that divides both 24 and 15 is 3.
In[6]:=
Click for copyable input
Out[6]=

The Kronecker delta function KroneckerDelta[n1,n2,] is equal to 1 if all the are equal, and is 0 otherwise. can be thought of as a totally symmetric tensor.

This gives a totally symmetric tensor of rank 3.
In[7]:=
Click for copyable input
Out[7]=
FactorInteger[n]a list of the prime factors of n, and their exponents
Divisors[n]a list of the integers that divide n
Prime[k]the k^(th) prime number
PrimePi[x]the number of primes less than or equal to x
PrimeQ[n]give True if n is a prime, and False otherwise
PrimeNu[n]the number of distinct primes in n
PrimeOmega[n]the number of prime factors counting multiplicities in n
LiouvilleLambda[n]the Liouville function
MangoldtLambda[n]the von Mandgoldt function
FactorInteger[n,GaussianIntegers->True]
a list of the Gaussian prime factors of the Gaussian integer n, and their exponents
PrimeQ[n,GaussianIntegers->True]give True if n is a Gaussian prime, and False otherwise

Integer factoring and related functions.

This gives the factors of 24 as , . The first element in each list is the factor; the second is its exponent.
In[8]:=
Click for copyable input
Out[8]=
Here are the factors of a larger integer.
In[9]:=
Click for copyable input
Out[9]=

You should realize that according to current mathematical thinking, integer factoring is a fundamentally difficult computational problem. As a result, you can easily type in an integer that the Wolfram Language will not be able to factor in anything short of an astronomical length of time. But as long as the integers you give are less than about 50 digits long, FactorInteger should have no trouble. And in special cases it will be able to deal with much longer integers.

Here is a rather special long integer.
In[10]:=
Click for copyable input
Out[10]=
The Wolfram Language can easily factor this special integer.
In[11]:=
Click for copyable input
Out[11]=

Although the Wolfram Language may not be able to factor a large integer, it can often still test whether or not the integer is a prime. In addition, the Wolfram Language has a fast way of finding the ^(th) prime number.

It is often much faster to test whether a number is prime than to factor it.
In[12]:=
Click for copyable input
Out[12]=
Here is a plot of the first 100 primes.
In[13]:=
Click for copyable input
Out[13]=
This is the millionth prime.
In[14]:=
Click for copyable input
Out[14]=

Particularly in number theory, it is often more important to know the distribution of primes than their actual values. The function PrimePi[x] gives the number of primes that are less than or equal to .

This gives the number of primes less than a billion.
In[15]:=
Click for copyable input
Out[15]=
PrimeNu gives the number of distinct primes.
In[16]:=
Click for copyable input
Out[16]=
PrimeOmega gives the number of prime factors counting multiplicities in n.
In[17]:=
Click for copyable input
Out[17]=
Liouville's function gives where is the number of prime factors counting multiplicity.
In[18]:=
Click for copyable input
Out[18]=
The Mangoldt function returns the log of prime power base or zero when composite.
In[19]:=
Click for copyable input
Out[19]=

By default, FactorInteger allows only real integers. But with the option setting GaussianIntegers->True, it also handles Gaussian integers, which are complex numbers with integer real and imaginary parts. Just as it is possible to factor uniquely in terms of real primes, it is also possible to factor uniquely in terms of Gaussian primes. There is nevertheless some potential ambiguity in the choice of Gaussian primes. In the Wolfram Language, they are always chosen to have positive real parts, and nonnegative imaginary parts, except for a possible initial factor of or .

Over the Gaussian integers, 2 can be factored as .
In[20]:=
Click for copyable input
Out[20]=
Here are the factors of a Gaussian integer.
In[21]:=
Click for copyable input
Out[21]=
PowerMod[a,b,n]the power modulo n
DirichletCharacter[k,j,n]the Dirichlet character
EulerPhi[n]the Euler totient function
MoebiusMu[n]the Möbius function
DivisorSigma[k,n]the divisor function
DivisorSum[n,form]the sum of for all i that divide n
DivisorSum[n,form,cond]the sum for only those divisors for which gives True
JacobiSymbol[n,m]the Jacobi symbol
ExtendedGCD[n1,n2,]the extended GCD of , ,
MultiplicativeOrder[k,n]the multiplicative order of k modulo n
MultiplicativeOrder[k,n,{r1,r2,}]the generalized multiplicative order with residues
CarmichaelLambda[n]the Carmichael function
PrimitiveRoot[n]a primitive root of n

Some functions from number theory.

The modular power function PowerMod[a,b,n] gives exactly the same results as Mod[a^b,n] for b>0. PowerMod is much more efficient, however, because it avoids generating the full form of .

You can use PowerMod not only to find positive modular powers, but also to find modular inverses. For negative b, PowerMod[a,b,n] gives, if possible, an integer such that . (Whenever such an integer exists, it is guaranteed to be unique modulo n.) If no such integer exists, the Wolfram Language leaves PowerMod unevaluated.

PowerMod is equivalent to using Power, then Mod, but is much more efficient.
In[22]:=
Click for copyable input
Out[22]=
This gives the modular inverse of 3 modulo 7.
In[23]:=
Click for copyable input
Out[23]=
Multiplying the inverse by 3 modulo 7 gives 1, as expected.
In[24]:=
Click for copyable input
Out[24]=
This finds the smallest nonnegative integer so that is equal to 3 mod 11.
In[25]:=
Click for copyable input
Out[25]=
This verifies the result.
In[26]:=
Click for copyable input
Out[26]=
This returns all integers less than 11 which satisfy the relation.
In[27]:=
Click for copyable input
Out[27]=
If d does not have a square root modulo n, PowerMod[d,n] will remain unevaluated and PowerModList will return an empty list.
In[28]:=
Click for copyable input
Out[28]=
In[29]:=
Click for copyable input
Out[29]=
This checks that 3 is not a square modulo 5.
In[30]:=
Click for copyable input
Out[30]=
Even for a large modulus, the square root can be computed fairly quickly.
In[31]:=
Click for copyable input
Out[31]=
PowerMod[d,n] also works for composite .
In[32]:=
Click for copyable input
Out[32]=

There are distinct Dirichlet characters for a given modulus k, as labeled by the index j. Different conventions can give different orderings for the possible characters.

DirichletCharacter works for very large numbers.
In[33]:=
Click for copyable input
Out[33]=

The Euler totient function gives the number of integers less than that are relatively prime to . An important relation (Fermat's little theorem) is that for all relatively prime to .

The Möbius function is defined to be if is a product of distinct primes, and if contains a squared factor (other than 1). An important relation is the Möbius inversion formula, which states that if for all , then , where the sums are over all positive integers that divide .

The divisor function is the sum of the ^(th) powers of the divisors of . The function gives the total number of divisors of , and is variously denoted , and . The function , equal to the sum of the divisors of , is often denoted .

For prime , .
In[34]:=
Click for copyable input
Out[34]=
The result is 1, as guaranteed by Fermat's little theorem.
In[35]:=
Click for copyable input
Out[35]=
This gives a list of all the divisors of 24.
In[36]:=
Click for copyable input
Out[36]=
gives the total number of distinct divisors of 24.
In[37]:=
Click for copyable input
Out[37]=

The function DivisorSum[n,form] represents the sum of for all i that divide n. DivisorSum[n,form,cond] includes only those divisors for which gives True.

This gives a list of sums for the divisors of five positive integers.
In[38]:=
Click for copyable input
Out[38]=
This imposes the condition that the value of each divisor i must be less than 6.
In[39]:=
Click for copyable input
Out[39]=

The Jacobi symbol JacobiSymbol[n,m] reduces to the Legendre symbol when is an odd prime. The Legendre symbol is equal to zero if is divisible by ; otherwise it is equal to if is a quadratic residue modulo the prime , and to if it is not. An integer relatively prime to is said to be a quadratic residue modulo if there exists an integer such that . The full Jacobi symbol is a product of the Legendre symbols for each of the prime factors such that .

The extended GCD ExtendedGCD[n1,n2,] gives a list where is the greatest common divisor of the , and the are integers such that . The extended GCD is important in finding integer solutions to linear Diophantine equations.

The first number in the list is the GCD of 105 and 196.
In[40]:=
Click for copyable input
Out[40]=
The second pair of numbers satisfies .
In[41]:=
Click for copyable input
Out[41]=

The multiplicative order function MultiplicativeOrder[k,n] gives the smallest integer such that . Then is known as the order of modulo . The notation is occasionally used.

The generalized multiplicative order function MultiplicativeOrder[k,n,{r1,r2,}] gives the smallest integer such that for some . MultiplicativeOrder[k,n,{-1,1}] is sometimes known as the suborder function of modulo , denoted . MultiplicativeOrder[k,n,{a}] is sometimes known as the discrete log of with respect to the base modulo .

The Carmichael function or least universal exponent gives the smallest integer such that for all integers relatively prime to .

ContinuedFraction[x,n]generate the first n terms in the continued fraction representation of x
FromContinuedFraction[list]reconstruct a number from its continued fraction representation
Rationalize[x,dx]find a rational approximation to x with tolerance dx

Continued fractions.

This generates the first 10 terms in the continued fraction representation for .
In[42]:=
Click for copyable input
Out[42]=
This reconstructs the number represented by the list of continued fraction terms.
In[43]:=
Click for copyable input
Out[43]=
The result is close to .
In[44]:=
Click for copyable input
Out[44]=
This gives directly a rational approximation to .
In[45]:=
Click for copyable input
Out[45]=

Continued fractions appear in many number theoretic settings. Rational numbers have terminating continued fraction representations. Quadratic irrational numbers have continued fraction representations that become repetitive.

ContinuedFraction[x]the complete continued fraction representation for a rational or quadratic irrational number
QuadraticIrrationalQ[x]test whether x is a quadratic irrational
RealDigits[x]the complete digit sequence for a rational number
RealDigits[x,b]the complete digit sequence in base b

Complete representations for numbers.

The continued fraction representation of starts with the term 8, then involves a sequence of terms that repeat forever.
In[46]:=
Click for copyable input
Out[46]=
This reconstructs from its continued fraction representation.
In[47]:=
Click for copyable input
Out[47]=
This number is a quadratic irrational.
In[48]:=
Click for copyable input
Out[48]=
This shows the recurring sequence of decimal digits in 3/7.
In[49]:=
Click for copyable input
Out[49]=
FromDigits reconstructs the original number.
In[50]:=
Click for copyable input
Out[50]=

Continued fraction convergents are often used to approximate irrational numbers by rational ones. Those approximations alternate from above and below, and converge exponentially in the number of terms. Furthermore, a convergent of a simple continued fraction is better than any other rational approximation with denominator less than or equal to .

Convergents[x]give a list of rational approximations of x
Convergents[x,n]give only the first n approximations

Continued fraction convergents.

This gives a list of rational approximations of 101/9801, derived from its continued fraction expansion.
In[51]:=
Click for copyable input
Out[51]=
This lists only the first 10 convergents.
In[52]:=
Click for copyable input
Out[52]=
This lists successive rational approximations to , until the numerical precision is exhausted.
In[53]:=
Click for copyable input
Out[53]=
With an exact irrational number, you have to explicitly ask for a certain number of terms.
In[54]:=
Click for copyable input
Out[54]=
LatticeReduce[{v1v2,}]a reduced lattice basis for the set of integer vectors
HermiteDecomposition[{v1,v2,}]the echelon form for the set of integer vectors

Functions for integer lattices.

The lattice reduction function LatticeReduce[{v1,v2,}] is used in several kinds of modern algorithms. The basic idea is to think of the vectors of integers as defining a mathematical lattice. Any vector representing a point in the lattice can be written as a linear combination of the form , where the are integers. For a particular lattice, there are many possible choices of the "basis vectors" . What LatticeReduce does is to find a reduced set of basis vectors for the lattice, with certain special properties.

Three unit vectors along the three coordinate axes already form a reduced basis.
In[55]:=
Click for copyable input
Out[55]=
This gives the reduced basis for a lattice in fourdimensional space specified by three vectors.
In[56]:=
Click for copyable input
Out[56]=

Notice that in the last example, LatticeReduce replaces vectors that are nearly parallel by vectors that are more perpendicular. In the process, it finds some quite short basis vectors.

For a matrix , HermiteDecomposition gives matrices and such that is unimodular, , and is in reduced row echelon form. In contrast to RowReduce, pivots may be larger than 1 because there are no fractions in the ring of integers. Entries above a pivot are minimized by subtracting appropriate multiples of the pivot row.

In this case, the original matrix is recovered because it was in row echelon form.
In[57]:=
Click for copyable input
Out[57]=
This satisfies the required identities.
In[58]:=
Click for copyable input
Out[58]=
Here the second matrix has some pivots larger than 1, and nonzero entries over pivots.
In[59]:=
Click for copyable input
Out[59]=
DigitCount[n,b,d]the number of d digits in the base b representation of n

Digit count function.

Here are the digits in the base 2 representation of the number 77.
In[60]:=
Click for copyable input
Out[60]=
This directly computes the number of ones in the base 2 representation.
In[61]:=
Click for copyable input
Out[61]=
The plot of the digit count function is selfsimilar.
In[62]:=
Click for copyable input
Out[62]=
BitAnd[n1,n2,]bitwise AND of the integers
BitOr[n1,n2,]bitwise OR of the integers
BitXor[n1,n2,]bitwise XOR of the integers
BitNot[n]bitwise NOT of the integer n
BitLength[n]number of binary bits in the integer n
BitSet[n,k]set bit k to 1 in the integer n
BitGet[n,k]get bit k from the integer n
BitClear[n,k]set bit k to 0 in the integer n
BitShiftLeft[n,k]shift the integer n to the left by k bits, padding with zeros
BitShiftRight[n,k]shift to the right, dropping the last k bits

Bitwise operations.

Bitwise operations act on integers represented as binary bits. BitAnd[n1,n2,] yields the integer whose binary bit representation has ones at positions where the binary bit representations of all of the have ones. BitOr[n1,n2,] yields the integer with ones at positions where any of the have ones. BitXor[n1,n2] yields the integer with ones at positions where or but not both have ones. BitXor[n1,n2,] has ones where an odd number of the have ones.

This finds the bitwise AND of the numbers 23 and 29 entered in base 2.
In[63]:=
Click for copyable input
Out[63]//BaseForm=

Bitwise operations are used in various combinatorial algorithms. They are also commonly used in manipulating bitfields in lowlevel computer languages. In such languages, however, integers normally have a limited number of digits, typically a multiple of 8. Bitwise operations in the Wolfram Language in effect allow integers to have an unlimited number of digits. When an integer is negative, it is taken to be represented in two's complement form, with an infinite sequence of ones on the left. This allows BitNot[n] to be equivalent simply to .

SquareFreeQ[n]give True if n does not contain a squared factor, False otherwise

Testing for a squared factor.

SquareFreeQ[n] checks to see if n has a square prime factor. This is done by computing MoebiusMu[n] and seeing if the result is zero; if it is, then n is not squarefree, otherwise it is. Computing MoebiusMu[n] involves finding the smallest prime factor q of n. If n has a small prime factor (less than or equal to ), this is very fast. Otherwise, FactorInteger is used to find q.

This product of primes contains no squared factors.
In[64]:=
Click for copyable input
Out[64]=
The square number 4 divides 60.
In[65]:=
Click for copyable input
Out[65]=
SquareFreeQ can handle large integers.
In[66]:=
Click for copyable input
Out[66]=
NextPrime[n]give the smallest prime larger than n
RandomPrime[{min,max}]return a random prime number between min and max
RandomPrime[max]return a random prime number less than or equal to max
RandomPrime[{min,max},n]return n random prime numbers between min and max
RandomPrime[max,n]return n random prime numbers less than or equal to max

Finding prime numbers.

NextPrime[n] finds the smallest prime p such that . For n less than 20 digits, the algorithm does a direct search using PrimeQ on the odd numbers greater than n. For n with more than 20 digits, the algorithm builds a small sieve and first checks to see whether the candidate prime is divisible by a small prime before using PrimeQ. This seems to be slightly faster than a direct search.

This gives the next prime after 10.
In[67]:=
Click for copyable input
Out[67]=
Even for large numbers, the next prime can be computed rather quickly.
In[68]:=
Click for copyable input
Out[68]=
This gives the largest prime less than 34.
In[69]:=
Click for copyable input
Out[69]=

For RandomPrime[{min,max}] and RandomPrime[max], a random prime p is obtained by randomly selecting from a prime lookup table if max is small and by a random search of integers in the range if max is large. If no prime exists in the specified range, the input is returned unevaluated with an error message.

Here is a random prime between 10 and 100.
In[70]:=
Click for copyable input
Out[70]=
PrimePowerQ[n]determine whether n is a positive integer power of a rational prime

Testing for involving prime powers.

The algorithm for PrimePowerQ involves first computing the least prime factor p of n and then attempting division by p until either 1 is obtained, in which case n is a prime power, or until division is no longer possible, in which case n is not a prime power.

Here is a number that is a power of a single prime.
In[71]:=
Click for copyable input
Out[71]=
Over the GaussianIntegers this is a prime power.
In[72]:=
Click for copyable input
Out[72]=
ChineseRemainder[list1,list2]give the smallest non-negative integer r with Mod[r,list2]==list1

Solving simultaneous congruences.

The Chinese remainder theorem states that a certain class of simultaneous congruences always has a solution. ChineseRemainder[list1,list2] finds the smallest nonnegative integer r such that Mod[r,list2] is . The solution is unique modulo the least common multiple of the elements of .

This means that , , and .
In[73]:=
Click for copyable input
Out[73]=
This confirms the result.
In[74]:=
Click for copyable input
Out[74]=
Longer lists are still quite fast.
In[75]:=
Click for copyable input
Out[75]=
PrimitiveRoot[n]give a primitive root of n, where n is a prime power or twice a prime power

Computing primitive roots.

PrimitiveRoot[n] returns a generator for the group of numbers relatively prime to n under multiplication . This has a generator if and only if n is 2, 4, a power of an odd prime, or twice a power of an odd prime. If n is a prime or prime power, the least positive primitive root will be returned.

Here is a primitive root of 5.
In[76]:=
Click for copyable input
Out[76]=
This confirms that it does generate the group.
In[77]:=
Click for copyable input
Out[77]=
Here is a primitive root of a prime power.
In[78]:=
Click for copyable input
Out[78]=
Here is a primitive root of twice a prime power.
In[79]:=
Click for copyable input
Out[79]=
If the argument is composite and not a prime power or twice a prime power, the function does not evaluate.
In[80]:=
Click for copyable input
Out[80]=
SquaresR[d,n]give the number of representations of an integer n as a sum of d squares
PowersRepresentations[n,k,p]give the distinct representations of the integer n as a sum of k non-negative p^(th) integer powers

Representing an integer as a sum of squares or other powers.

Here are the representations of 101 as a sum of 3 squares.
In[81]:=
Click for copyable input
Out[81]=