Arithmetic Functions from Factorization

Functions on Positive Integers

An arithmetic function is a function whose domain is the positive integers. It assigns a value to each integer

$$ n\in\mathbb{N}. $$

Typical examples include the number of positive divisors of $n$, the sum of positive divisors of $n$, and the number of integers less than or equal to $n$ that are coprime to $n$.

Prime factorization makes many arithmetic functions computable. Once we know

$$ n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}, $$

we can often calculate the value of the function directly from the primes $p_i$ and exponents $\alpha_i$.

The Divisor Counting Function

The divisor counting function is denoted by

$$ \tau(n). $$

It counts the number of positive divisors of $n$.

For example, the positive divisors of $12$ are

$$ 1,2,3,4,6,12. $$

Hence

$$ \tau(12)=6. $$

Now suppose

$$ n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}. $$

Every positive divisor $d\mid n$ has the form

$$ d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_r^{\beta_r}, $$

where

$$ 0\le \beta_i\le \alpha_i. $$

For each prime $p_i$, there are $\alpha_i+1$ choices for the exponent $\beta_i$. Therefore

$$ \tau(n)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1). $$

For example,

$$ 360=2^3\cdot3^2\cdot5. $$

Thus

$$ \tau(360)=(3+1)(2+1)(1+1)=24. $$

So $360$ has $24$ positive divisors.

The Divisor Sum Function

The divisor sum function is denoted by

$$ \sigma(n). $$

It is defined by

$$ \sigma(n)=\sum_{d\mid n} d. $$

For example, the positive divisors of $12$ are

$$ 1,2,3,4,6,12, $$

so

$$ \sigma(12)=1+2+3+4+6+12=28. $$

Prime factorization gives a closed formula. If

$$ n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}, $$

then

$$ \sigma(n) = (1+p_1+p_1^2+\cdots+p_1^{\alpha_1}) \cdots (1+p_r+p_r^2+\cdots+p_r^{\alpha_r}). $$

Each factor is a finite geometric sum, so

$$ 1+p+\cdots+p^\alpha = \frac{p^{\alpha+1}-1}{p-1}. $$

Hence

$$ \sigma(n) = \prod_{i=1}^{r} \frac{p_i^{\alpha_i+1}-1}{p_i-1}. $$

For example,

$$ 12=2^2\cdot3. $$

Therefore

$$ \sigma(12) = (1+2+2^2)(1+3) = 7\cdot4 = 28. $$

Euler's Totient Function

Euler's totient function is denoted by

$$ \varphi(n). $$

It counts the number of integers $k$ satisfying

$$ 1\le k\le n $$

and

$$ \gcd(k,n)=1. $$

For example, the integers from $1$ to $10$ that are coprime to $10$ are

$$ 1,3,7,9. $$

Thus

$$ \varphi(10)=4. $$

If

$$ n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}, $$

then

$$ \varphi(n) = n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right). $$

For a prime power,

$$ \varphi(p^\alpha)=p^\alpha-p^{\alpha-1}=p^\alpha\left(1-\frac1p\right), $$

because the only integers from $1$ to $p^\alpha$ not coprime to $p^\alpha$ are the multiples of $p$.

For example,

$$ 12=2^2\cdot3. $$

Thus

$$ \varphi(12) = 12\left(1-\frac12\right)\left(1-\frac13\right) = 12\cdot\frac12\cdot\frac23 = 4. $$

Indeed, the integers $1,5,7,11$ are the positive integers at most $12$ that are coprime to $12$.

Multiplicative Functions

An arithmetic function $f$ is called multiplicative if

$$ f(ab)=f(a)f(b) $$

whenever

$$ \gcd(a,b)=1. $$

Many important arithmetic functions are multiplicative, including

$$ \tau(n),\qquad \sigma(n),\qquad \varphi(n). $$

This property explains why prime factorization gives product formulas. If

$$ n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}, $$

then the prime powers

$$ p_1^{\alpha_1},\ldots,p_r^{\alpha_r} $$

are pairwise coprime. Therefore, for a multiplicative function $f$,

$$ f(n)=f(p_1^{\alpha_1})\cdots f(p_r^{\alpha_r}). $$

Thus one can understand $f(n)$ by understanding its values on prime powers.

Prime-Power Reduction

Prime-power reduction is a recurring method in number theory.

Instead of studying an arithmetic function on all positive integers at once, one first computes

$$ f(p^\alpha) $$

for prime powers. Then multiplicativity extends the formula to all $n$.

For example,

$$ \tau(p^\alpha)=\alpha+1, $$

because the positive divisors are

$$ 1,p,p^2,\ldots,p^\alpha. $$

Similarly,

$$ \sigma(p^\alpha)=1+p+p^2+\cdots+p^\alpha. $$

And

$$ \varphi(p^\alpha)=p^\alpha-p^{\alpha-1}. $$

These three prime-power formulas determine the three functions completely.

Role in Number Theory

Arithmetic functions translate prime factorization into numerical invariants. They measure different aspects of the divisor structure of an integer.

The function $\tau(n)$ counts divisors. The function $\sigma(n)$ sums divisors. The function $\varphi(n)$ measures coprimality. Each function reveals different information about how $n$ is built from primes.

This point of view leads naturally to Dirichlet convolution, Möbius inversion, average orders, Euler products, and analytic number theory.