14. Even More on Positive Divisors

The outline of the this notebook is as follows:

Today we will spend time looking at the functions \tau which counts the number of positive the divisors of n and \sigma which is the sum of positive divisors of n.  Our goal is, once again, to use our minds, paper and pencil, and SageMath to combine to not just conjecture, but start to give logical reasons for our conjectures.

Definition: An arithmetic function is real or complex f defined on the set of positive integers. That is f : \mathbb{Z}_{>0}\to\mathbb{C}. An arithmetic function f is said to be multiplicative if it is not identically zero and if

f(a\,b) = f(a)\,f(b) \quad \text{ whenever } \gcd(a,\,b) = 1.

Let a and b be positive integers and f : \mathbb{Z}_{>0}\to\mathbb{C} is an arithmetic function. If \gcd(a,\,b)=1 and f(a\,b) = f(a)\,f(b) then f is said to be an multiplicative.

f is said to be completely multiplicative if f(a\,b) = f(a)\,f(b) for all a,b \in \mathbb{N}.

Knowing the definition of \tau and what it means for an arithmetic function to be multiplicative, can we proof that \tau and \sigma are both multiplicative function?

Let us first consider \tau. To prove that \tau is a multiplicative function, we must ask ourselves the following questions.

  1. Is \tau an arithmetic function?

    • Yes \tau is an arithmetic function by definition. In particular, for all n \in \mathbb{N}, \tau(n) \in \mathbb{N} and since \mathbb{N} \subset \mathbb{C}, it follows that \tau is an arithmetic function.

  2. For any two positive integers a and b with \gcd(a,b) = 1, is \tau(a\,b) = \tau(a)\,\tau(b)?

    • We want to count the number of divisors of the product a\,b given that \gcd(a,b)=1. From \gcd(a,b) = 1, we know that a does not divide b and vice-versa. Therefore, for a given divisor of a say a_{1}, the set divisors of the product a\,b will be a_{1} multiplied by all the divisors of b. That is, the set \{a_{1} k \, | \, k \text{ divides } b\} with cardinality \tau(b). Repeating this for all the divisors of a is exactly the product \tau(a) \, \tau(b). This completes the proof.

How will you define \tau in SageMath?

def tau(n):
    r"""
    Returns the number of divisors of $n$.
    """
    return number_of_divisors(n)

tau(48)==tau(8)*tau(6)

False

Oops! What just happened? I thought we just proved that \tau was multiplicative. What went wrong here?

Can you think of questions that we could explore on the number of divisors function \tau?

  • If n is prime, what is \tau(n)?

  • Is tau(sum of 2 perfect squares) even or odd?

  • What is \tau(n) if n is a perfect square. Is there a pattern?

Possible questions to guide us to obtain a general formular for the arithmetic function \tau(n) for any positive integer n.

  • If p is prime, what is the number of divisors of p, \tau(p)? Is there a general formula?

  • If p and q are prime, what is \tau(p\,q)?

  • If p is prime, what is the number of divisors of p^{k} for k=2,3,\dots,10? Is there a general formula for \tau(p^{k}) for all positive integer k?

  • Given a positive integer n, is there a general formula for the number of divisors? Is there a general formula for \tau(n)?

tau_of_prime_powers = lambda p, n : table([(p^k, tau(p^k) == k+1) for k in [0..n]], header_row=["$p^k$", r"$[\tau(p^k) = k+1]$"])

tau_of_prime_powers(3, 10)

prime_range(10)

[tau_of_prime_powers(p,10) for p in prime_range(10)]

Conjecture: If p is prime then for all k \in \mathbb{N}, \tau(p^{k}) = k+1. Let us work in groups to proof this now.

Proof:

We have a proof for our conjecture so it is now a theorem. But I will want to call it Lemma 1: If p is prime, then for all k \in \mathbb{N}, \tau(p^{k}) = k+1.

Now let we want to derive a general formula for \tau(n) for all positive integers. We know from the Fundamental Theorem of Arithmetic that:

Every positive integer can be written as a finite product of powers of distinct primes. That is, n = \prod_{i=1}^{k} p^{e_{i}}_{i}.

Using this result and the multiplicative property of \tau, we are able to derive a formula for \tau given any positive integer n.

How would you derive such a formula for \tau given a positive integer n? Let n be any positive integer. We want to derive a formula for \tau(n). By the fundamental theorem of arithmetic

n = \prod_{i=1}^{k} p^{e_{i}}_{i}.

Then

\tau(n) = \tau\left( \prod_{i=1}^{k} p^{e_{i}}_{i}\right) = \tau(p^{e_{1}}_{1} \, p^{e_{2}}_{2} \cdots p^{e_{k}}_{k}) =\tau(p^{e_{1}}_{1}) \,  \tau(p^{e_{2}}_{2}) \cdots \tau(p^{e_{k}}_{k}) = (e_{1} + 1)\, (e_{2} + 1) \cdots (e_{k} + 1) = \prod_{i=1}^{k}(e_{i} + 1).

Hence we have derived the general formula \tau given any positive integer n.

14.1. General Formulas

Here is the general hint to follow in order to get a general formula for these arithmetic functions.

  • Formula for \tau or \sigma for primes

  • Formula for \tau or \sigma for a power of a prime

  • General formula for \tau or \sigma

Observe that these are the steps we followed to obtain a general formula for the number of divisors function \tau.

In mathematics, a perfect square say x is the product of some integer say y with itself. That is, x = y^{2}.

  • Investigate on the number of divisors of perfect squares using SageMath.

  • Observe your data very closely and try and come up with a conjecture on a pattern you think will always be true.

  • Proof your conjecture.

You are encouraged to work in groups.

Right now, try working on your own or in groups to try to prove the following conjectures.

  • For a perfect square n^{2}, \tau(n^2) is odd.

(For a full proof, you will probably need a reason why only certain numbers can divide other numbers.)

Now use the procedure we followed to derive a formula for \tau to derive a formula for \sigma for any positive integer n.

Let us recal the definition of \sigma. It is defined as follows: Given a positive n, \sigma(n) is the sum of all the positive divisors of n.

  • Check if \sigma is multiplicative, that is,

    \sigma(a\,b) = \sigma(a)\,\sigma(b)\qquad \text{whenever } \gcd(a,\,b)=1.

    If it is multiplicative, then try to prove it.

How will you define \sigma in SageMath?

def sigma(n):
    """
    Returns the sum of the divisors of `n`
    """
    pass

Can you formulate questions about the sum of positive divisors of n, \sigma(n), that we could explore?

  • Write your questions here.

It turns out that sometimes it is also useful to have functions adding up just certain divisors.  For instance, one could write a function \tau_o(n) for just the odd divisors, and \tau_e(n) for just the even divisors.  Or you could define \tau_1(n) and \tau_3(n) to be the functions giving the number of divisors which are congruent to 1 (mod 4) and 3 (mod 4), respectively.

Try doing a few of these as well.  You will likely want to recall how to use filtered list comprehensions, or “if/else” statements in a loop.

Naturally, I strongly encourage you to make interactive cells if this proves useful to you!

14.2. Exploring Divisors

Anyway, you should spend quite a bit of time today to try to find more patterns - or prove them! The kinds of questions here are somewhat different from those with partitions.

14.2.1. Modulo/Congruerence

It turns out that there are some pleasant patterns for when \tau and \sigma are even and odd. I encourage you to explore and give arguments for what you find. Try to prove the conjectures that you come up with.

  • One could also investigate whether there are patterns when n is even or odd.  What happens to \tau(n)+\sigma(n)?

  • Write a program to demonstrate that \sigma(n)=2\,n if and only if the sums of the reciprocals of its (positive) divisors equals 2. Give an algebraic reason why this works.

  • Investigate the values for \tau(n) or \sigma(n) modulo other primes p.  It would be interesting to see if there are any useful conjectures here.