Number Theoretic Functions

Some of the built-in functions that are useful for doing number theoretic work
are the following.

Mod[k,n] : computes the remainder when k is divided by n.

Quotient[k,n]: Gives the integer quotient defined by Floor[k/n].

GCD[n1,n2,...]: Gives the greatest common divisor of the arguments.

PrimeQ[n]: Returns True if the number is prime and False otherwise.

Prime[k]: Gives the kth prime.

FactorInteger[ n]: Returns the prime factorization of n. The function is only suitable
for integers less than 10^12.

Other useful functions are PowerMod and EulerPhi.

Here are a few examples of using these functions.

In[42]:=

In[43]:=

  
  PrimeQ[ 2^61 -1]

Out[43]=

  True

This shows that 2^61 -1 is prime. Use of PrimeQ is not a proof that a number is
prime. For proofs of primality of a number, consult your number theory textbook.

In[44]:=

  FactorInteger[ 1234567]

Out[44]=

  {{127, 1}, {9721, 1}}

The result of FactorInteger is a list of the prime factors and the exponent to which
that prime occurs in the factorization. In the above, 1234567 = 127 * 9721.

FactorInteger is limited to about 12-15 digits and for numbers with more digits other
methods are required. Consult your number theory book for details on other methods.
Many functions such as Divisors, DivisorSigma and EulerPhi depend on FactorInteger,
hence they too are restricted in the size of the input.

For small numbers, we can verify if a number n is prime by dividing it
by all primes up to sqrt(n). This is a good illustration of combining Mathematica functions.
Let us verify that 9721 is Prime. We compute the primes up to sqrt(9721) using the following c
commands.

In[45]:=

  
  n=9721;
  k=N[ Sqrt[9721]]
  
  numprimes= PrimePi[ k]
  
  listofprimes= Table[ Prime[ i], { i, 1, numprimes}]

Out[45]=

  98.5951

Out[46]=

  25

Out[47]=

  {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 
    89, 97}

Next, we can divide 9721 by all these numbers. Many Mathematica functions
are Listable, that is, they can take a list as an argument and apply the function
to each element. ( The same thing would require the use of loop structures in
other languages.) The Table command and few other list related functions are discussed in
the following section.

In[48]:=

  Mod[ n, listofprimes]

Out[48]=

  {1, 1, 1, 5, 8, 10, 14, 12, 15, 6, 18, 27, 4, 
    3, 39, 22, 45, 22, 6, 65, 12, 4, 10, 20, 21}

We computed the remainder when n is divided by all the primes up to square root of
n and we see that all the remainders are non-zero. This proves that the number 9721
is prime.

Exercise: Verify that 7927 and 47419 are primes by using this division method.

This method is not suitable for large numbers. More efficient methods for large primes
are discussed in your textbook.

Up to Tutorial