Skip to content

Arithmetic Functions from Factorization

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

number-theory book chatgpt

Functions on Positive Integers

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

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

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

Prime factorization makes many arithmetic functions computable. Once we know

n=p1α1p2α2⋯prαr, 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 pip_i and exponents αi\alpha_i.

The Divisor Counting Function

The divisor counting function is denoted by

τ(n). \tau(n).

It counts the number of positive divisors of nn.

For example, the positive divisors of 1212 are

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

Hence

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

Now suppose

n=p1α1p2α2⋯prαr. n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}.

Every positive divisor d∣nd\mid n has the form

d=p1β1p2β2⋯prβr, d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_r^{\beta_r},

where

0≤βi≤αi. 0\le \beta_i\le \alpha_i.

For each prime pip_i, there are αi+1\alpha_i+1 choices for the exponent βi\beta_i. Therefore

τ(n)=(α1+1)(α2+1)⋯(αr+1). \tau(n)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1).

For example,

360=23⋅32⋅5. 360=2^3\cdot3^2\cdot5.

Thus

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

So 360360 has 2424 positive divisors.

The Divisor Sum Function

The divisor sum function is denoted by

σ(n). \sigma(n).

It is defined by

σ(n)=∑d∣nd. \sigma(n)=\sum_{d\mid n} d.

For example, the positive divisors of 1212 are

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

so

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

Prime factorization gives a closed formula. If

n=p1α1p2α2⋯prαr, n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r},

then

σ(n)=(1+p1+p12+⋯+p1α1)⋯(1+pr+pr2+⋯+prαr). \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+⋯+pα=pα+1−1p−1. 1+p+\cdots+p^\alpha = \frac{p^{\alpha+1}-1}{p-1}.

Hence

σ(n)=∏i=1rpiαi+1−1pi−1. \sigma(n) = \prod_{i=1}^{r} \frac{p_i^{\alpha_i+1}-1}{p_i-1}.

For example,

12=22⋅3. 12=2^2\cdot3.

Therefore

σ(12)=(1+2+22)(1+3)=7⋅4=28. \sigma(12) = (1+2+2^2)(1+3) = 7\cdot4 = 28.

Euler’s Totient Function

Euler’s totient function is denoted by

φ(n). \varphi(n).

It counts the number of integers kk satisfying

1≤k≤n 1\le k\le n

and

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

For example, the integers from 11 to 1010 that are coprime to 1010 are

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

Thus

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

If

n=p1α1p2α2⋯prαr, n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r},

then

φ(n)=n∏i=1r(1−1pi). \varphi(n) = n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right).

For a prime power,

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

because the only integers from 11 to pαp^\alpha not coprime to pαp^\alpha are the multiples of pp.

For example,

12=22⋅3. 12=2^2\cdot3.

Thus

φ(12)=12(1−12)(1−13)=12⋅12⋅23=4. \varphi(12) = 12\left(1-\frac12\right)\left(1-\frac13\right) = 12\cdot\frac12\cdot\frac23 = 4.

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

Multiplicative Functions

An arithmetic function ff is called multiplicative if

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

whenever

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

Many important arithmetic functions are multiplicative, including

τ(n),σ(n),φ(n). \tau(n),\qquad \sigma(n),\qquad \varphi(n).

This property explains why prime factorization gives product formulas. If

n=p1α1⋯prαr, n=p_1^{\alpha_1}\cdots p_r^{\alpha_r},

then the prime powers

p1α1,…,prαr p_1^{\alpha_1},\ldots,p_r^{\alpha_r}

are pairwise coprime. Therefore, for a multiplicative function ff,

f(n)=f(p1α1)⋯f(prαr). f(n)=f(p_1^{\alpha_1})\cdots f(p_r^{\alpha_r}).

Thus one can understand f(n)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α) f(p^\alpha)

for prime powers. Then multiplicativity extends the formula to all nn.

For example,

τ(pα)=α+1, \tau(p^\alpha)=\alpha+1,

because the positive divisors are

1,p,p2,…,pα. 1,p,p^2,\ldots,p^\alpha.

Similarly,

σ(pα)=1+p+p2+⋯+pα. \sigma(p^\alpha)=1+p+p^2+\cdots+p^\alpha.

And

φ(pα)=pα−pα−1. \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 τ(n)\tau(n) counts divisors. The function σ(n)\sigma(n) sums divisors. The function φ(n)\varphi(n) measures coprimality. Each function reveals different information about how nn is built from primes.

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