# 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.