Divisors from Prime Factorization

1. The Number of Divisors: $\tau (n)$

Let's begin by defining the functions we'll be working with.

To derive a formula for $\tau (n)$, the key insight is to consider the structure of a divisor based on the prime factorization of $n$.

Suppose $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$. If $d$ is a divisor of $n$, what can we say about the prime factorization of $d$? By the FTA, any prime factor of $d$ must also be a prime factor of $n$. This means that $d$ must be of the form:
$d=p_1^{f_1}{p}_2^{f_2}\cdots p_k^{f_k}$
Furthermore, for $d$ to divide $n$, the exponent of each prime in $d$ cannot exceed the corresponding exponent in $n$. This gives us the crucial constraint: for each $i$ from 1 to $k$, we must have $0\le f_i\le e_i$.

This transforms the problem of counting divisors into a simple combinatorial counting problem. For each prime factor $p_i$, we need to choose an exponent $f_i$.

• For the prime $p_1$, the exponent $f_1$ can be any integer from 0 to $e_1$. This gives us $e_1+1$ choices.
• For the prime $p_2$, the exponent $f_2$ can be any integer from 0 to $e_2$. This gives us $e_2+1$ choices.
• ...and so on, up to $p_k$, for which we have $e_k+1$ choices for the exponent $f_k$.

Since the choice of each exponent is independent, the total number of ways to form a divisor $d$ is the product of the number of choices for each exponent. The uniqueness guaranteed by the FTA ensures that each distinct combination of exponents produces a distinct divisor.

This leads directly to the formula for $\tau (n)$. The following resource provides a concise, formal statement and proof of this result.

So, for $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$, the number of positive divisors is:
$\tau (n)=(e_1+1)(e_2+1)\cdots (e_k+1)$

For instance, consider $n=72=2^3\cdot 3^2$. Here $e_1=3$ and $e_2=2$. The number of divisors is $\tau (72)=(3+1)(2+1)=4\times 3=12$.

2. The Sum of Divisors: $\sigma (n)$

Deriving the formula for the sum of divisors, $\sigma (n)$, requires a slightly more subtle algebraic insight, but it flows from the same principle: analyzing the structure of divisors.

Let's consider our example $n=72=2^3\cdot 3^2$ again. The twelve divisors are all numbers of the form $2^a{3}^b$ where $a\in \{0,1,2,3\}$ and $b\in \{0,1,2\}$. To find their sum, we need to compute:
$\sigma (72)={\sum }_{a=0}^3{\sum }_{b=0}^2{2}^a{3}^b$
Writing out this sum term-by-term can be cumbersome. Instead, let's consider the following product:
$(2^0+2^1+2^2+2^3)\times (3^0+3^1+3^2)$
If you apply the distributive property to expand this product, each term in the expansion will be the product of one term from the first parenthesis and one term from the second. For example, you would get terms like $2^0\cdot 3^0$, $2^0\cdot 3^1$, $2^1\cdot 3^0$, $2^3\cdot 3^2$, and so on.

Critically, you will find that the terms generated by this expansion are precisely the twelve unique divisors of 72. The expanded form of the product is exactly the sum of all divisors. This insight is the key to the formula for $\sigma (n)$.

The following article walks through this derivation beautifully, starting with a simple example and generalizing the result.

Generalizing this, for any integer $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$, the sum of its divisors is given by the product:
$\sigma (n)=(1+p_1+\cdots +p_1^{e_1})(1+p_2+\cdots +p_2^{e_2})\cdots (1+p_k+\cdots +p_k^{e_k})$
Each term in this product, $(1+p_i+\cdots +p_i^{e_i})$, is a finite geometric series. You are likely familiar with the formula for its sum, but a quick review is always helpful.

Using the formula for the sum of a geometric progression, $1+r+\cdots +r^k=\frac{r^{k+1}-1}{r-1}$, we can write our expression for $\sigma (n)$ in a more compact and elegant form.

This gives us our final formula. For $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$, the sum of positive divisors is:
$\sigma (n)={\prod }_{i=1}^k(1+p_i+\cdots +p_i^{e_i})={\prod }_{i=1}^k\frac{p_i^{e_i+1}-1}{p_i-1}$

3. An Alternative View: Multiplicative Functions

The derivation above is beautifully constructive. It builds the formula directly from the structure of the divisors. There is another, slightly more abstract path to the same result that introduces an important concept in number theory: multiplicative functions.

A function $f$ on the positive integers is called multiplicative if $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime (i.e., $\gcd (m,n)=1$).

It can be shown from the definitions that both $\tau (n)$ and $\sigma (n)$ are multiplicative functions. If we can prove this property first, the general formulas follow easily.

1. First, prove $f$ is multiplicative.
2. Second, find a formula for $f$ on prime powers, $f(p^k)$.
3. Combine these results. Since $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$ and all the $p_i^{e_i}$ terms are pairwise coprime, we have $f(n)=f(p_1^{e_1})f(p_2^{e_2})\cdots f(p_k^{e_k})$.

This approach is powerful because it separates the problem into proving a general structural property (multiplicativity) and solving a simpler special case (prime powers). The following video provides a clear proof for $\sigma (n)$ using this method. The argument for why $\sigma (n)$ is multiplicative relies on a combinatorial bijection, a style of reasoning that is very common in Olympiad mathematics.

Seeing both the constructive derivation (expanding the product) and the property-based derivation (proving multiplicativity) gives you a more robust and flexible understanding of why these formulas hold.

Conclusion

In this lesson, we have leveraged the Fundamental Theorem of Arithmetic to derive two of the most important formulas in elementary number theory.

Key Takeaways:

• The structure of any divisor of an integer $n$ is completely determined by the prime factorization of $n$.
• If $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$, the number of divisors is found by a combinatorial argument:
  $\tau (n)=(e_1+1)(e_2+1)\cdots (e_k+1)$
• The sum of divisors is found by recognizing the sum as the expansion of a product of geometric series:
  $\sigma (n)=\left(\frac{p_1^{e_1+1}-1}{p_1-1}\right)\left(\frac{p_2^{e_2+1}-1}{p_2-1}\right)\cdots \left(\frac{p_k^{e_k+1}-1}{p_k-1}\right)$
• Both $\tau (n)$ and $\sigma (n)$ are multiplicative functions, a property which provides an alternative and powerful way to derive their formulas.

We have now seen not only why prime factorization is unique but also how that uniqueness provides the foundation for powerful quantitative tools. In our next lesson, we will continue to explore the consequences of the FTA by examining how the exponents in a prime factorization can be used to characterize special types of numbers, such as perfect squares, cubes, and higher powers.