We examine a class of interesting functions used in number theory.

THE TAU FUNCTION

The function τ(n) counts how many divisors n has. This count includes 1 and n. (τ is a Greek letter and is called “tau.”) The first few values are τ(1) = 1, τ(2) = 2, τ(3) = 2, τ(4) = 3, τ(5) = 2, τ(6) = 4, τ(7) = 2, τ(8) = 4, τ(9) = 3, and τ(10) = 4.

Let n have the prime decomposition . It is easy to see that m is a divisor of n if and only if where 0 ≤ c ₁ ≤ e ₁, 0 ≤ c ₂ ≤ e ₂, 0 ≤ c ₃ ≤ e ₃, …, 0 ≤ c_r  ≤ e_r . (This can be stated more tersely as “0 ≤ c_i  ≤ e_i for i = 1, 2, …, r.”) As an example, the divisors of 2³3²7¹ = 8 × 9 × 7 = 504 have the form 2 ^a 3 ^b 7 ^c , where a = 0, 1, 2, or 3; b = 0, 1, or 2; and c = 0 or 1. In general, there are e ₁ + 1 values for c ₁ (including 0); e ₂ + 1 values for c ₂, …; and e_r  + 1 values for c_r . This implies the following simple formula for computing τ(n):

(6.1)

Here is an interesting theorem about τ.

Let us compute the product of the divisors of n. If n is not a square, there are an even number of divisors, half of which are less than . For each such divisor, d, there is another divisor greater than . Their product is , and there are τ/2 such pairs. Then the product of the divisors of n is . To illustrate this, let n = 18. Then τ(18) = 6 and the 6 divisors are 1, 2, 3, 6, 9, and 18. We group them into τ/2 or 3 pairs: 1 and 18, 2 and 9, and 3 and 6, each of which has product 18. Then the product of all the divisors of 18 is .

If n is a square, then τ is odd. Then let τ = 2k + 1. Then there are k divisors less than . For each such divisor, d, there is another divisor , which is greater than . Their product is n and there are k such pairs. Then there is the divisor . The product of all the divisors is, therefore, . We have proved the following elegant theorem.

Since half of the divisors of n are less than or equal to , we have an upper bound for τ(n).

This upper bound is quite high. When n = 100, for example, it says that τ(100) ≤ 20, while, in fact, τ(100) = τ(2² × 5²) = 3 × 3 = 9.

THE SIGMA FUNCTION

The sum of the divisors of n is denoted σ(n). (Lowercase “sigma.”) This is often written , where the summation is over all d such that d | n, as stated below the sigma sign. The first few values of σ(n) are given by σ(1) = 1, σ(2) = 1 + 2 = 3, σ(3) = 1 + 3 = 4, σ(5) = 1 + 5 = 6, σ(6) = 1 + 2 + 3 + 6 = 12, σ(7) = 1 + 7 = 8, and σ(9) = 1 + 3 + 9 = 13. To find a formula for σ(n), we need a few observations. If n = p^rq^s , where p and q are prime, then , since the terms of this product yield all the divisors of n, such as pq ². This extends to the more general case where . Then .

Note that each parenthesis contains a geometric progression. The sum of a geometric progression, , is given by , as we proved in Chapter 1. Then we have the following expression for σ(n):

(6.2)

MULTIPLICATIVE FUNCTIONS

τ(n) and σ(n) are examples of multiplicative functions. A multiplicative function, f, satisfies:

1. f(1) = 1.
2. f(mn) = f(m)f(n) whenever gcd(m,n) = 1.

If f is a nonidentically zero function satisfying condition 2, it can be easily shown (see the exercises at the end of the chapter) that condition 1 must be true.

That τ and σ are multiplicative follows immediately from (6.1) and (6.2). Other examples of multiplicative functions are the “identity” function, I(n) = n, and the constant function, C(n) = 1.

PERFECT NUMBERS REVISITED

Recall that a perfect number is the sum of its proper divisors. It follows that n is perfect if and only if σ(n) = 2n, since σ counts n as a divisor. For example, the perfect number 6 satisfies σ(6) = 1 + 2 + 3 + 6 = 12 = 2 × 6. It was stated in Chapter 1 that if is prime, then 2 ⁿ⁻¹(2 ⁿ  − 1) is perfect. We shall prove this using the multiplicative property of σ.

On the other hand, we will show that if an even number is perfect, then it must be of the form 2 ⁿ⁻¹(2 ⁿ  − 1), where 2 ⁿ  − 1 is prime. We will make use of the multiplicative nature of σ.

MERSENNE PRIMES

The next theorem supplies a necessary condition for 2 ⁿ  − 1 to be prime. This condition is useful in narrowing down the search for Mersenne primes.

The fact that n is prime does not guarantee that 2 ⁿ  − 1 will be prime. When n = 11, for example, 23 | 2¹¹ − 1.

F(n) = ∑f(d) WHERE d IS A DIVISOR OF n

Given a multiplicative function, f, we define a related function, F, by the formula . In other words, , where d ₁, d ₂, …, d_τ are the divisors of n. It is quite interesting that F(n) is also multiplicative, as the next theorem asserts.

The next to the last equality, , is hard to verify. It might be easier to write out the two sums on the right and then do the multiplication. Thus, , for example, is , and . Then the product of these sums will yield rs terms of the form dd′, where d is one of the r divisors of m and d′ is one of the s divisors of n. This is precisely .

, while , so τ and σ are multiplicative!

Our next theorem will require manipulating sums. Bear in mind that to each divisor, d, of a given number n, there is a unique divisor , such that the product of these two divisors is n. As d assumes the values of all the divisors of n in increasing order, assumes the values of all the divisors of n in decreasing order. The following chart demonstrates this for n = 30. The product of the entries of each row is, of course, 30.

If we let g be the constant function, C(n) = 1 in the above theorem, we get the result of the previous theorem, that is, is multiplicative.

The values of a multiplicative function, f, are completely determined by its values for integers of the form p^k , where p is a prime, since implies that .

THE MÖBIUS FUNCTION

The so-called Möbius function, denoted μ(n), is defined as follows:

1. μ(1) = 1.
2. μ(n) = 0 if p ² | n for any prime p.
3. μ(n) = (−1) ^r if n = p ₁ p ₂…p_r .

The first few values of μ(n) are μ(1) = 1, μ(2) = −1, μ(3) = −1, μ(4) = 0 (since 2² | 4), μ(5) = −1, μ(6) = 1, μ(7) = −1, μ(8) = 0 (since 2² | 8), μ(9) = 0 (since 3² | 9), and μ(10) = 1. If n > 1, it must be square-free for μ(n) to be nonzero. (A number is called square-free if its only square divisor is 1. Thus, for example, 10 is square-free, while 18 is not square-free since 9 | 18.) This is why #3 above assumes that n = p ₁ p ₂…p_r .

Here is a theorem about μ. We present two proofs, each as interesting as the theorem.

One of the reasons that μ is important in number theory is given by the next theorem, often called the Möbius inversion formula. We omit the proof.

Letting f(d) = C(d) = 1, we know that g(n) = τ(n), as noted earlier in the chapter. Then we obtain the beautiful identity

Letting f(d) = I(d) = d, we obtain g(n) = σ(n), in which case we have

THE RIEMANN ZETA FUNCTION

The Riemann zeta function is defined by where s is a complex number with certain restrictions. This function is very important in a number of branches of mathematics and has been studied extensively. In this elementary text, we will restrict s to positive integer values and will only get a tiny glimpse of this deep and mysterious function. When s = 1, we obtain a divergent series, that is, a series whose partial sums get larger and larger without bound. The partial sums approach infinity, as we will see. Formally, . Now, observe the following inequalities:

Continuing in this manner, we see that a partial sum of ζ(1) can be made as large as we please by accumulating enough consecutive sequences of terms that exceed . The series is called the harmonic series, and its divergence to infinity was known in the fourteenth century.

The eighteenth-century mathematician Euler showed, using calculus, that , that is,

(6.3)

Consider the infinite product , where the factors are of the form , as p ranges over all the primes. Let’s calculate ζ(2) × P. We will do this by multiplying by one factor of P at a time:

Thus, multiplication by removes every term whose denominator is divisible by 2. Now, multiply the right side of this equation by the next factor, :

Multiplication by removes every term whose denominator is divisible by 3. Now, we multiply the right side of this equation by the next factor, :

Multiplication by removes every term whose denominator is divisible by 5. As we continue this multiplication, we remove more terms. In fact, each term except 1 eventually gets removed. We conclude that ζ(2) × P = 1. Using (6.3), we then see that (approximately .608). We are now ready to state and prove a beautiful theorem.

We shall not prove it in this text, but is also the probability that a randomly chosen positive integer is square-free. Furthermore, the probability that three randomly chosen integers do not share a common divisor is the reciprocal of ζ(3) (approximately .832).

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

1. Find τ(300) by finding all the divisors of 300 and counting them. Then use the formula. Do the same for τ(1000). See the programs at the end of the chapter.
2. Describe all numbers n, such that τ(n) = 6. What is the smallest such n?
3. Describe all numbers n, such that τ(n) = 12. What is the smallest such n?
4. ^*Given any positive integer m, show that there exists a positive integer, n, such that τ(n) = m.
5. ^*Show that if m ≥ 2 in the previous exercise, then there exist infinitely many n’s with τ(n) = m.
6. Find σ(1000) by adding all the divisors of 1000. Then use the formula.
7. Find σ(p ³), where p is prime, (i) directly from the definition and (ii) using formula (6.2). Reconcile your answers.
8. Show that if n = 2 ^k , where k ≥ 1, then σ(n) = 2n − 1.
9. Assuming that a function, f, such that f(k) ≠ 0 for all k ≥ 1, satisfies f(mn) = f(m)f(n) whenever gcd(m,n) = 1, show that f(1) = 1.
10. How does it follow from formulas (6.1) and (6.2) that τ and σ are multiplicative?
11. Show that the identity function, I(n) = n, and the constant function, C(n) = 1, are multiplicative.
12. Show that the function f(n) = n^k , where k is a nonnegative integer, is multiplicative. How does this apply to the previous exercise?
13. If f and g are multiplicative, show that fg and f/g (if f/g is defined) are also multiplicative.
14. ^*Let f be a multiplicative function that is not identically zero. Show that , where p ₁, p ₂, …, p_r are the prime divisors of n.
15. ^*Let . Show using the previous exercise that:
    1. .
    2. .
    3. .
    4. .
16. If n is a perfect number, show that .
17. Show that 6 is the only square-free even perfect number.
18. Show that p^k , where p is prime, is not a perfect number.
19. If m is an even perfect number greater than 6, show that m = 4 (mod 6).
20. The harmonic mean, H, of the n numbers a ₁, a ₂, …, a_n is defined by the equation . Write a program to obtain the harmonic mean of any given set of numbers. Find the harmonic mean of various sets of consecutive integers and try to develop an idea of where it falls.
21. Show that the harmonic mean of the divisors of an even perfect number is an integer.
22. The geometric mean of the n numbers a ₁, a ₂, …, a_n is . Write a program to obtain the geometric mean of any given set of numbers. Compare it to the harmonic mean after computing several examples of both for various sets of integers.
23. ^*A number is called multiplicatively perfect if it is the product of its proper divisors. If p is a prime, show that p ³ is multiplicatively perfect. Are there other examples less than 1000?
24. ^*Show that semiprimes are multiplicatively perfect. (A semiprime is the product of two primes.)
25. ^* r and s are amicable numbers if each is the sum of the proper divisors of the other, that is, if r = σ(s) − s and s = σ(r) − r. Let a = 3 × 2 ⁿ  − 1, b = 3 × 2 ⁿ⁻¹ − 1, and c = 9 × 2²ⁿ⁻¹ − 1, where n ≥ 2. If a, b, and c are prime, show that 2 ⁿab and 2 ⁿc are amicable numbers. Note that when n = 2, we get the amicable pair 220 and 284, known to the Pythagoreans.
26. Find μ(n) for all n ≤ 200.
27. ^*Show that μ(n)μ(n + 1)μ(n + 2)μ(n + 3) = 0 for all n ≥ 1.
28. Find .
29. ^* ω(n) is the number of distinct prime divisors of n. Also, ω(1) = 0. Show that if gcd(m,n) = 1, then ω(mn) = ω(m) + ω(n). Use this to show that 2 ^ω(n) is multiplicative.
30. Show that .
31. ^*Show that counts the number of square-free divisors of n.
32. Show that every positive integer can be written as mn ², where m is square-free. Write a program to do this.
33. ^*Let r ≥ 0. Define . Show that σ_r (n) is multiplicative.
34. Show that τ(n) = σ ₀(n) and σ(n) = σ ₁(n).
35. Show that , where p is a prime.
36. Let f be a multiplicative function such that . Find f(n).
37. Let f and g be multiplicative functions such that f(p^k ) = g(p^k ) for all primes, p, and for all k ≥ 1. Show that f(n) = g(n) for all n.
38. Prove that .
39. ^*Ramanujan called a number n highly composite if τ(k) < τ(n) for all k < n. The first few highly composite numbers are 2, 4, 6, and 12. Find the next 100 such numbers.
40. ^*It is known that . Verify this formula for n ≤ 20.
41. By letting n = p ^k−1, where p is prime, show that the identity is a special case of the remarkable formula of the previous exercise.
42. ^*Let . Show that .
43. ^*Let s ≥ 2. Show that .
44. ^*Prove that there are infinitely many pairs of consecutive square-free numbers as follows:
    1. Assume to the contrary that there are only finitely many pairs of square-free numbers. Why would it follow that there is an integer N such that there are no pairs of consecutive square-free numbers larger than N?
    2. As a consequence of the preceding assumption, show that it would follow that at least half of all numbers larger than N are not square-free.
    3. Show that this would contradict the fact (stated without proof in the chapter) that the probability that a randomly chosen positive integer is square-free is .
45. Write a program to find all pairs of consecutive square-free numbers up to any given number n.
46. ^*Given the consecutive integers a and a + 1, there are infinitely many pairs, x and x + 1, such that a | x and a + 1 | x + 1. When a = 3, for example, the integers x = 15 and x + 1 = 16 have the property that 3 | x and 4 | x + 1. Write a program to find arbitrarily many solutions, x and x + 1, for a given pair of consecutive integers a and a + 1.
47. ^*Find the smallest positive integer, n, such that τ(n) = m, where m is a given positive integer.
48. ^*Note that σ(3) = 1 + 3 = 4 = 2² and σ(22) = 1 + 2 + 11 + 22 = 36 = 6². Find all numbers n ≤ 2000 for which σ(n) is a square.
49. ^*A perfect number, n, satisfies σ(n) = 2n. This has been generalized to multiply perfect numbers satisfying σ(n) = kn where k > 2. Find all n ≤ 1000 for which σ(n) = 3n.
50. ^*The number 12 has the curious property that the product of its proper divisors equals its square, that is, 1 × 2 × 3 × 4 × 6 = 144 = 12². Find all n ≤ 100 with this property.
51. Verify that 9,363,584 and 9,437,056 are amicable numbers, that is, verify that each is the sum of the proper divisors of the other.
52. ^*Let f(n) be the sum of the proper divisors of n. Furthermore, define f^k (n) as follows. Let f ¹(n) = f(n), f ²(n) = f[f(n)], f ³(n) = f[f[f(n)]], etc. Show that when n = 12,496, we have f ⁵(12,496) = n = 12,496, thereby forming a so-called amicable chain of length 5.
53. ^*If n = 14,316 in the previous exercise, show that we obtain an amicable chain of length 28, that is, show that f ²⁸(14,316) = n = 14,316.
54. ^*Let . Define f^k (n) as in the two preceding exercises. It is conjectured that given n, there exists a k such that f^k (n) = 1. Verify this for n ≤ 1000. Note that f(1) = 2 and f(2) = 1. The sequence n, f ¹(n), f ²(n), f ³(n), … is the orbit of n under f. The orbit of 1 under f is 1, 2, 1, 2, …. An orbit consisting of a repeated sequence of values is periodic. The conjecture says that the orbit of any n gets “pulled” into the periodic orbit 1, 2, 1, 2, ….
55. ^*Let . It has been conjectured that given any positive integer n, there exists a k such that f^k (n) = 1. Verify this for all n ≤ 100. Given an n, its orbit under the action of this function is called a juggler sequence.
56. Write a program to compute the sum of the first k terms of ζ(n) for given positive integers n and k. Show that your answer for ζ(4) approaches π ⁴/90 as k gets large. It is known that when n is even, ζ(n) is a rational multiple of πⁿ . Not much is known about ζ(n) when n is odd.
57. ^*Observe that the consecutive triple, 33, 34, and 35, consists of semiprimes, that is, each member of the triple is the product of two primes. Find the next four consecutive triples with this property.

Stand-Alone Program Listing the Proper Factors

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<head>
<title>Return proper factors</title>
<script>

function produceFactors(n){
  var ans = [];  //start off with empty array
  for (var i=1;i<n;i++){
    if ((n%i)==0){
      ans.push(i);
    }
  } 
  return ans;
}
function getfactors(){
  placeref = document.getElementById("place");
  messages = "The proper factors are <br/>";
  n = parseInt(document.f.num.value);
  factors = produceFactors(n);
  for (var i=0;i<factors.length;i++){
    messages +=String(factors[i])+"<br/>";
  }
  placeref.innerHTML = messages;
  return false;
}
</script>
</head>
<body>
Produce list of proper factors:
<form name="f" onsubmit="return getfactors();">
 <input type="number" name="num" value=""/>
 <input type="submit" value="Enter integer"/>

</form>
<div id="place">
List of factors will go here.
</div>
</body>
</html>

Tau from the Definition

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Tau</title>
<script>
function produceFactors(n){
  var ans = [];  //start off with empty array
  for (var i=1;i<=n;i++){
    if ((n%i)==0){
       ans.push(i);    
    }
  }  
  return ans;
}
function tau(){
  placeref = document.getElementById("place");
  n = parseInt(document.f.num.value);  
  t = produceFactors(n).length; 
  messages = "The value of tau for "+ String(n)+" is "+
String(t);
  placeref.innerHTML = messages;
  return false;
}
</script>
</head>
<body>
Enter number to see its tau value:
<form name="f" onSubmit="return tau();">
 <input type="number" name="num" value=""/>
 <input type="submit" value="Enter integer"/>
</form>
<div id="place">

Answer will go here.
</div>
</body>
</html>

Prime Decomposition File to Be Included Using External Script Element

// JavaScript 
 
 
function produceFactors(n){
  var ans = [];  //start off with empty array
  //notice start with 2, not 1
  for (var i=2;i<=n;i++){
    if ((n%i)==0){
      ans.push(i);


    }
  }

  return ans;
}
function onlyprimes(factors){
  var ans = [];
  for (var i=0;i<factors.length;i++){
    if (isPrime(factors[i])){
      ans.push(factors[i]);
    }
  }
  return ans;
}
function buildPrimeDecomposition(n) {
  var table = [];  //each element will be an array of length 2
  var m = n;
  var facs = produceFactors(n);
    while (facs.length>0){
      f = facs[0];   //always using first, that is, 0th //element
      if ((m % f)>0) {
          //f, the ith element of facs does NOT //divide m

          facs.shift();  //remove this factor
      }
      else {
        m = m / f;
        e=1;
        //need to see if exponent is more than 1
        while (0 == (m%f) ){
          m = m /f;
          e++;
        }
        table.push ([f,e]);
        facs.shift();
      }
 
    }
    return table;
}
function isPrime(n){
   var lim = Math.sqrt(n);
   for (var i=2;i<=lim;i++){
     if (0 == n % i){
       return false;
     }
   }
   return true;
}

Tau from Formula

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Tau from formula</title>
<script type="text/javascript" src="primeDecomposition.js"> </script>
<script>
function tauFF(){
  var table;
  placeref = document.getElementById("place");
  n = parseInt(document.f.num.value);
  table = buildPrimeDecomposition(n);

  t = 1;
  for (var i=0;i<table.length;i++){
    t = t * (1+table[i][1]);
  }
  messages = "The value of tau for "+ String(n)+" is "+ String(t);
  placeref.innerHTML = messages;
  return false;
}
</script>
</head>
<body>
Enter number to see its tau value:
<form name="f" onSubmit="return tauFF();">
 <input type="number" name="num" value=""/>
 <input type="submit" value="Enter integer"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>