**3.2.4 Integer and Number-Theoretical Functions**

Some integer functions.

The remainder on dividing by

.
In[1]:= **Mod[17, 3]**

Out[1]=

The integer part of

.
In[2]:= **Quotient[17, 3]**

Out[2]=

Mod also works with real numbers.
In[3]:= **Mod[5.6, 1.2]**

Out[3]=

The result from Mod always has the same sign as the second argument.
In[4]:= **Mod[-5.6, 1.2]**

Out[4]=

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

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 largest integer that divides both 24 and 15 is 3.
In[5]:= **GCD[24, 15]**

Out[5]=

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[6]:= **FactorInteger[24]**

Out[6]=

Here are the factors of a larger integer.
In[7]:= **FactorInteger[111111111111111111]**

Out[7]=

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. As long as the integers you give are less than about 20 digits long, FactorInteger should have no trouble. Only in special cases, however, will it 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.)

Here is a rather special long integer.
In[8]:= **30!**

Out[8]=

Mathematica can easily factor this special integer.
In[9]:= **FactorInteger[%]**

Out[9]=

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.

It is often much faster to test whether a number is prime than to factor it.
In[10]:= **PrimeQ[234242423]**

Out[10]=

Here is a plot of the first 100 primes.
In[11]:= **ListPlot[ Table[ Prime[n], {n, 100} ] ]**

This is the millionth prime.
In[12]:= **Prime[1000000]**

Out[12]=

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[13]:= **PrimePi[10^9]**

Out[13]=

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[14]:= **FactorInteger[2, GaussianIntegers -> True]**

Out[14]=

Here are the factors of a Gaussian integer.
In[15]:= **FactorInteger[111 + 78 I, GaussianIntegers -> True]**

Out[15]=

Some functions from number theory.

The modular power functionPowerMod[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.

PowerMod is equivalent to using Power, then Mod, but is much more efficient.
In[16]:= **PowerMod[2, 13451, 3]**

Out[16]=

This gives the modular inverse of 3 modulo 7.
In[17]:= **PowerMod[3, -1, 7]**

Out[17]=

Multiplying the inverse by 3 modulo 7 gives 1, as expected.
In[18]:= **Mod[3 %, 7]**

Out[18]=

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 often denoted . The function , equal to the sum of the divisors of , is often denoted

.

For prime ,

.
In[19]:= **EulerPhi[17]**

Out[19]=

The result is 1, as guaranteed by Fermat's Little Theorem.
In[20]:= **PowerMod[3, %, 17]**

Out[20]=

This gives a list of all the divisors of 24.
In[21]:= **Divisors[24]**

Out[21]=

gives the total number of distinct divisors of 24.
In[22]:= **DivisorSigma[0, 24]**

Out[22]=

The Jacobi symbolJacobiSymbol[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[m,n] gives a list

g,

r,s

where is the greatest common divisor of and , and and 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[23]:= **ExtendedGCD[105, 196]**

Out[23]=

The second pair of numbers satisfies

.
In[24]:= **15 105 - 8 196**

Out[24]=

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. The vector representing each 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[25]:= **LatticeReduce[{{1,0,0},{0,1,0},{0,0,1}}]**

Out[25]=

This gives the reduced basis for a lattice in four-dimensional space specified by three vectors.
In[26]:= **LatticeReduce[{{1,0,0,12345}, {0,1,0,12435},**

{0,0,1,12354}}]

Out[26]=

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.