:tocdepth: 2

.. _even_more_on_positive_divisors:

Even More on Positive Divisors
============================================================================

.. contents:: :local:

.. highlight:: python

The outline of the this notebook is as follows:

Today we will spend time looking at the functions :math:`\tau` which
counts the number of positive the divisors of :math:`n` and
:math:`\sigma` which is the sum of positive divisors of :math:`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 :math:`f` defined
on the set of positive integers. That is
:math:`f : \mathbb{Z}_{>0}\to\mathbb{C}`. An arithmetic function
:math:`f` is said to be multiplicative if it is not identically zero and
if

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

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

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

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

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

.. raw:: html

   <ol>

.. raw:: html

   <li>

Is :math:`\tau` an arithmetic function?

.. raw:: html

   </li>

.. raw:: html

   <ul>

.. raw:: html

   <li>

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

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   <li>

For any two positive integers :math:`a` and :math:`b` with
:math:`\gcd(a,b) = 1`, is :math:`\tau(a\,b) = \tau(a)\,\tau(b)`?

.. raw:: html

   <ul>

.. raw:: html

   <li>

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

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   </li>

.. raw:: html

   </ol>

How will you define :math:`\tau` in *SageMath*?

.. code:: ipython3

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


.. code:: ipython3

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




.. parsed-literal::

    False



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



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

-  If :math:`n` is prime, what is :math:`\tau(n)`?
-  Is tau(sum of 2 perfect squares) even or odd?
-  What is :math:`\tau(n)` if n is a perfect square. Is there a pattern?

.. raw:: html

   <hr>

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

-  If :math:`p` is prime, what is the number of divisors of :math:`p`,
   :math:`\tau(p)`? Is there a general formula?
-  If :math:`p` and :math:`q` are prime, what is :math:`\tau(p\,q)`?
-  If :math:`p` is prime, what is the number of divisors of
   :math:`p^{k}` for :math:`k=2,3,\dots,10`? Is there a general formula
   for :math:`\tau(p^{k})` for all positive integer :math:`k`?
-  Given a positive integer :math:`n`, is there a general formula for
   the number of divisors? Is there a general formula for
   :math:`\tau(n)`?

.. code:: ipython3

    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]$"])

.. code:: ipython3

    tau_of_prime_powers(3, 10)

.. code:: ipython3

    prime_range(10)

.. code:: ipython3

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

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

Proof:

.. raw:: html

   <p>

.. raw:: html

   </p>

.. raw:: html

   <p>

.. raw:: html

   </p>

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

.. raw:: html

   <p>

.. raw:: html

   </p>

.. raw:: html

   <p>

.. raw:: html

   </p>

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

.. raw:: html

   <p style="margin-left: 30px;">

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

.. raw:: html

   </p>

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

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

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

Then

.. math:: \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 :math:`\tau` given any
positive integer :math:`n`.

General Formulas
~~~~~~~~~~~~~~~~

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

.. raw:: html

   <ul>

.. raw:: html

   <li>

Formula for :math:`\tau` or :math:`\sigma` for primes

.. raw:: html

   </li>

.. raw:: html

   <li>

Formula for :math:`\tau` or :math:`\sigma` for a power of a prime

.. raw:: html

   </li>

.. raw:: html

   <li>

General formula for :math:`\tau` or :math:`\sigma`

.. raw:: html

   </li>

.. raw:: html

   </ul>

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

In mathematics, a perfect square say :math:`x` is the product of some
integer say :math:`y` with itself. That is, :math:`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 :math:`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 :math:`\tau`
to derive a formula for :math:`\sigma` for any positive integer
:math:`n`.

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

-  Check if :math:`\sigma` is *multiplicative*, that is,

   .. math:: \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 :math:`\sigma` in *SageMath*?

.. code:: ipython3

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

Can you formulate questions about the sum of positive divisors of
:math:`n`, :math:`\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
:math:`\tau_o(n)` for just the odd divisors, and :math:`\tau_e(n)` for
just the even divisors.  Or you could define :math:`\tau_1(n)` and
:math:`\tau_3(n)` to be the functions giving the number of divisors
which are congruent to :math:`1` (mod :math:`4`) and :math:`3` (mod
:math:`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!



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.

Modulo/Congruerence
^^^^^^^^^^^^^^^^^^^

It turns out that there are some pleasant patterns for when :math:`\tau`
and :math:`\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 :math:`\tau(n)+\sigma(n)`?

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

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