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 m/n) |
| 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 ni are pairwise relatively prime |
| GCD[n1,n2,...] | the greatest common divisor of n1, n2, ... |
| LCM[n1,n2,...] | the least common multiple of n1, n2, ... |
| KroneckerDelta[n1,n2,...] | the Kronecker delta  n1n2... equal to 1 if all the ni 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.
| Out[1]= |  |
|
The integer part of 17/3.
| Out[2]= |  |
|
Mod also works with real numbers.
| Out[3]= |  |
|
The result from Mod always has the same sign as the second argument.
| Out[4]= |  |
|
For any integers
a and
b, it is always true that
b*Quotient[a, b]+Mod[a, b] is equal to
a.
| Mod[k,n] | result in the range 0 to n-1 |
| Mod[k,n,1] | result in the range 1 to n |
| Mod[k,n,-n/2] | result in the range  -n/2 to  +n/2 |
| Mod[k,n,d] | result in the range d to d+n-1 |
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.
| Out[5]= |  |
|
The greatest common divisor function
GCD[n1, n2, ...] gives the largest integer that divides all the
ni exactly. When you enter a ratio of two integers,
Mathematica 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
ni.
The largest integer that divides both 24 and 15 is 3.
| Out[6]= |  |
|
The Kronecker delta function
KroneckerDelta[n1, n2, ...] is equal to 1 if all the
ni are equal, and is 0 otherwise.
n1n2... can be thought of as a totally symmetric tensor.
This gives a totally symmetric tensor of rank 3.
| Out[7]= |  |
|
Integer factoring and related functions.
This gives the factors of 24 as 23, 31. The first element in each list is the factor; the second is its exponent.
| Out[8]= |  |
|
Here are the factors of a larger integer.
| 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
Mathematica 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.
| Out[10]= |  |
|
Mathematica can easily factor this special integer.
| Out[11]= |  |
|
Although
Mathematica may not be able to factor a large integer, it can often still test whether or not the integer is a prime. In addition,
Mathematica has a fast way of finding the
kth prime number.
It is often much faster to test whether a number is prime than to factor it.
| Out[12]= |  |
|
Here is a plot of the first 100 primes.
| Out[13]= |  |
|
This is the millionth prime.
| 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
(x) that are less than or equal to
x.
This gives the number of primes less than a billion.
| Out[15]= |  |
|
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
Mathematica, they are always chosen to have positive real parts, and non-negative imaginary parts, except for a possible initial factor of
-1 or
±i.
Over the Gaussian integers, 2 can be factored as (-i) (1+i)2.
| Out[16]= |  |
|
Here are the factors of a Gaussian integer.
| Out[17]= |  |
|
| PowerMod[a,b,n] | the power ab modulo n |
| EulerPhi[n] | the Euler totient function  (n) |
| MoebiusMu[n] | the Möbius function  (n) |
| DivisorSigma[k,n] | the divisor function  k (n) |
| JacobiSymbol[n,m] | the Jacobi symbol  |
| ExtendedGCD[n1,n2,...] | the extended gcd of n1, n2, ... |
| MultiplicativeOrder[k,n] | the multiplicative order of k modulo n |
| MultiplicativeOrder[k,n,{r1,r2,...}] |
| the generalized multiplicative order with residues ri |
| CarmichaelLambda[n] | the Carmichael function  (n) |
| 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
a^b.
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
k such that
ka-b
1modn. (Whenever such an integer exists, it is guaranteed to be unique modulo
n.) If no such integer
k exists,
Mathematica leaves
PowerMod unevaluated.
| Out[18]= |  |
|
This gives the modular inverse of 3 modulo 7.
| Out[19]= |  |
|
Multiplying the inverse by 3 modulo 7 gives 1, as expected.
| Out[20]= |  |
|
This finds the smallest non-negative integer x so that x2 is equal to 3 mod 11.
| Out[21]= |  |
|
This verifies the result.
| Out[22]= |  |
|
This returns all integers less than 11 which satisfy the relation.
| Out[23]= |  |
|
If d does not have a square root modulo n, PowerMod[d, n] will remain unevaluated and PowerModList will return an empty list.
| Out[24]= |  |
|
This checks that 3 is not a square modulo 5.
| Out[25]= |  |
|
Even for a large modulus, the square root can be computed fairly quickly.
| Out[26]= |  |
|
PowerMod[d, n] also works for composite n.
| Out[27]= |  |
|
The Euler totient function
(n) gives the number of integers less than
n that are relatively prime to
n. An important relation (Fermat's Little Theorem) is that
a (n)1modn for all
a relatively prime to
n.
The Möbius function
(n) is defined to be
(-1)k if
n is a product of
k distinct primes, and
0 if
n contains a squared factor (other than 1). An important relation is the Möbius inversion formula, which states that if
for all
n, then
, where the sums are over all positive integers
d that divide
n.
The divisor function
k (n) is the sum of the
kth powers of the divisors of
n. The function
0 (n) gives the total number of divisors of
n, and is variously denoted
d (n),
(n) and
(n). The function
1 (n), equal to the sum of the divisors of
n, is often denoted
(n).
For prime n, (n)=n-1.
| Out[28]= |  |
|
The result is 1, as guaranteed by Fermat's Little Theorem.
| Out[29]= |  |
|
This gives a list of all the divisors of 24.
| Out[30]= |  |
|
0 (n) gives the total number of distinct divisors of 24.
| Out[31]= |  |
|
The Jacobi symbol
JacobiSymbol[n, m] reduces to the Legendre symbol
when
m is an odd prime. The Legendre symbol is equal to zero if
n is divisible by
m, otherwise it is equal to
1 if
n is a quadratic residue modulo the prime
m, and to
-1 if it is not. An integer
n relatively prime to
m is said to be a quadratic residue modulo
m if there exists an integer
k such that
k2nmodm. The full Jacobi symbol is a product of the Legendre symbols
for each of the prime factors
pi such that
.
The extended gcd
ExtendedGCD[n1, n2, ...] gives a list
{g, {r1, r2, ...}} where
g is the greatest common divisor of the
ni, and the
ri are integers such that
g=r1n1+r2n2+.... 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.
| Out[32]= |  |
|
The second pair of numbers satisfies g=rm+sn.
| Out[33]= |  |
|
The multiplicative order function
MultiplicativeOrder[k, n] gives the smallest integer
m such that
km1modn. The function is sometimes known as the index or discrete log of
k. The notation
ordn (k) is occasionally used.
The generalized multiplicative order function
MultiplicativeOrder[k, n, {r1, r2, ...}] gives the smallest integer
m such that
kmrimodn for some
i.
MultiplicativeOrder[k, n, {-1, 1}] is sometimes known as the suborder function of
k modulo
n, denoted
sordn (k).
The Carmichael function or least universal exponent
(n) gives the smallest integer
m such that
km1modn for all integers
k relatively prime to
n.
| 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 .
| Out[34]= |  |
|
This reconstructs the number represented by the list of continued fraction terms.
| Out[35]= |  |
|
The result is close to .
| Out[36]= |  |
|
This gives directly a rational approximation to .
| Out[37]= |  |
|
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.
| Out[38]= |  |
|
This reconstructs  from its continued fraction representation.
| Out[39]= |  |
|
This number is a quadratic irrational.
| Out[40]= |  |
|
This shows the recurring sequence of decimal digits in 3/7.
| Out[41]= |  |
|
| Out[42]= |  |
|
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
p/q of a simple continued fraction is better than any other rational approximation with denominator less than or equal to
q.
| 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.
| Out[43]= |  |
|
This lists only the first 10 convergents.
| Out[44]= |  |
|
This lists successive rational approximations to , until the numerical precision is exhausted.
| Out[45]= |  |
|
With an exact irrational number, you have to explicitly ask for a certain number of terms.
| Out[46]= |  |
|
| LatticeReduce[{v1,v2,...}] | a reduced lattice basis for the set of integer vectors vi |
| HermiteDecomposition[{v1,v2,...}] | the echelon form for the set of integer vectors vi |
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
vk 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
ck vk, where the
ck are integers. For a particular lattice, there are many possible choices of the "basis vectors"
vk. 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.
| Out[47]= |  |
|
This gives the reduced basis for a lattice in four-dimensional space specified by three vectors.
| Out[48]= |  |
|
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
m,
HermiteDecomposition gives matrices
u and
r such that
u is unimodular,
u.m=r, and
r 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.
| Out[49]= |  |
|
This satisfies the required identities.
| Out[50]= |  |
|
Here the second matrix has some pivots larger than 1, and nonzero entries over pivots.
| Out[51]= |  |
|
| 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.
| Out[52]= |  |
|
This directly computes the number of ones in the base 2 representation.
| Out[53]= |  |
|
The plot of the digit count function is self-similar.
| Out[54]= |  |
|
| BitAnd[n1,n2,...] | bitwise AND of the integers ni |
| BitOr[n1,n2,...] | bitwise OR of the integers ni |
| BitXor[n1,n2,...] | bitwise XOR of the integers ni |
| 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
ni have ones.
BitOr[n1, n2, ...] yields the integer with ones at positions where any of the
ni have ones.
BitXor[n1, n2] yields the integer with ones at positions where
n1 or
n2 but not both have ones.
BitXor[n1, n2, ...] has ones where an odd number of the
ni have ones.
This finds the bitwise AND of the numbers 23 and 29 entered in base 2.
Out[55]//BaseForm= |
| |  |
|
Bitwise operations are used in various combinatorial algorithms. They are also commonly used in manipulating bitfields in low-level computer languages. In such languages, however, integers normally have a limited number of digits, typically a multiple of 8. Bitwise operations in
Mathematica 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
-1-n.
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
1223), this is very fast. Otherwise,
FactorInteger is used to find
q.
This product of primes contains no squared factors.
| Out[56]= |  |
|
The square number 4 divides 60.
| Out[57]= |  |
|
| Out[58]= |  |
|
| 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
p>n. 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.
| Out[59]= |  |
|
Even for large numbers, the next prime can be computed rather quickly.
| Out[60]= |  |
|
This gives the largest prime less than 34.
| Out[61]= |  |
|
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.
| Out[62]= |  |
|
| 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
n 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.
| Out[63]= |  |
|
| Out[64]= |  |
|
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 non-negative integer
r such that
Mod[r, list2] is
list1. The solution is unique modulo the least common multiple of the elements of
list2.
This means that 2440 mod 4, 2441 mod 9, and 2442 mod 121.
| Out[65]= |  |
|
This confirms the result.
| Out[66]= |  |
|
Longer lists are still quite fast.
| Out[67]= |  |
|
| 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
mod n. 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.
| Out[68]= |  |
|
This confirms that it does generate the group.
| Out[69]= |  |
|
Here is a primitive root of a prime power.
| Out[70]= |  |
|
Here is a primitive root of twice a prime power.
| Out[71]= |  |
|
If the argument is composite and not a prime power or twice a prime power, the function does not evaluate.
| Out[72]= |  |
|
| 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 pth 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.
| Out[73]= |  |
|
list1
