3.2.5 Integer and Number-Theoretical Functions

Mod[k, n]	k modulo n (remainder from dividing k by n)
Quotient[m, n]	the quotient of m and n (integer part of m/n)
GCD[, , ... ]	the greatest common divisor of , , ...
LCM[, , ... ]	the least common multiple of , , ...
KroneckerDelta[, , ... ]	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

The remainder on dividing by .

In[1]:=  Mod[17, 3] Out[1]=

The integer part of .

In[2]:=  Quotient[17, 3] Out[2]=

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
Mod[k, n, 1]	result in the range 1 to
Mod[k, n, -n/2]	result in the range to
Mod[k, n, d]	result in the range to

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 part of the list, with the list treated cyclically.

In[5]:=  Part[{a, b, c}, Mod[18, 3, 1]] Out[5]=

The greatest common divisor function GCD[, , ... ] gives the largest integer that divides all the 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[, , ... ] gives the smallest integer that contains all the factors of each of the .

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

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 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
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

This gives the factors of 24 as , . The first element in each list is the factor; the second is its exponent.

In[8]:=  FactorInteger[24] Out[8]=

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. (You can make some factoring problems go faster by setting the option FactorComplete->False, so that FactorInteger[n] tries to pull out only easy factors from n.)

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 k prime number.

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 .

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 or .

Over the Gaussian integers, 2 can be factored as .

In[16]:=  FactorInteger[2, GaussianIntegers -> True] Out[16]=

PowerMod[a, b, n]	the power modulo
EulerPhi[n]	the Euler totient function
MoebiusMu[n]	the Möbius function
DivisorSigma[k, n]	the divisor function
JacobiSymbol[n, m]	the Jacobi symbol
ExtendedGCD[, , ... ]	the extended gcd of , , ...
MultiplicativeOrder[k, n]	the multiplicative order of modulo
MultiplicativeOrder[k, n, {, , ... }]
	the generalized multiplicative order with residues
CarmichaelLambda[n]	the Carmichael function
LatticeReduce[{, , ... }]	the reduced lattice basis for the set of integer vectors

The modular power function PowerMod[a, b, n] gives exactly the same results as Mod[a^b, n] for . 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 such that . (Whenever such an integer exists, it is guaranteed to be unique modulo .) If no such integer exists, Mathematica leaves PowerMod unevaluated.

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 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[21]:=  EulerPhi[17] Out[21]=

gives the total number of distinct divisors of 24.

In[24]:=  DivisorSigma[0, 24] Out[24]=

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[, , ... ] gives a list {g, {, , ... }} 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 second pair of numbers satisfies .

In[26]:=  -13 105 + 7 196 Out[26]=

The multiplicative order function MultiplicativeOrder[k, n] gives the smallest integer such that . The function is sometimes known as the index or discrete log of . The notation is occasionally used.

The generalized multiplicative order function MultiplicativeOrder[k, n, {, , ... }] gives the smallest integer such that for some . MultiplicativeOrder[k, n, {-1, 1}] is sometimes known as the suborder function of modulo , denoted .

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

The lattice reduction function LatticeReduce[{, , ... }] 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.

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.

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

This generates the first 10 terms in the continued fraction representation for .

In[29]:=  ContinuedFraction[Pi, 10] Out[29]=

The result is close to .

In[31]:=  N[%] Out[31]=

This gives directly a rational approximation to .

In[32]:=  Rationalize[Pi, 1/1000] Out[32]=

Continued fractions appear in many number-theoretical 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
RealDigits[x]	the complete digit sequence for a rational number
RealDigits[x, b]	the complete digit sequence in base b

The continued fraction representation of starts with the term 8, then involves a sequence of terms that repeat forever.

In[33]:=  ContinuedFraction[Sqrt[79]] Out[33]=

This reconstructs from its continued fraction representation.

In[34]:=  FromContinuedFraction[%] Out[34]=

This shows the recurring sequence of decimal digits in .

In[35]:=  RealDigits[3/7] Out[35]=

DigitCount[n, b, d]

the number of d digits in the base b representation of n

BitAnd[, , ... ]	bitwise AND of the integers
BitOr[, , ... ]	bitwise OR of the integers
BitXor[, , ... ]	bitwise XOR of the integers
BitNot[n]	bitwise NOT of the integer n

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

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 .