Examples of arithmetic functions

Skip to main content

Section 2.1 Examples of arithmetic functions

Definition 2.1.1.

An arithmetic function is a function with domain

N = {1, 2, \dots}

and codomain the complex numbers

C .

Here are a number of arithmetic functions:

$ϕ$ Euler totient: $ϕ (n)$ is the number of $k$ such that $1 \leq k \leq n$ and $(n, k) = 1$
$d (n) :$ number of positive divisors of $n .$ $d (n) = \sum_{k ∣ n} 1 .$ (This function is also often denoted $τ .$ )
$σ$ sum of positive divisors of $n .$ $σ (n) = \sum_{k ∣ n} k .$
$1 (n) = 1$ for all $n .$ (In Crisman’s book this function was denoted $u .$ )
$N (n) = n$ for all $n$
$e (n) = {\begin{cases} 1 & if n = 1 \\ 0 & otherwise \end{cases} .$ (In Crisman’s book this function was denoted $I .$ )
$σ_{s} (n) = \sum_{k ∣ n} k^{s} .$ So $d = σ_{0},$ $σ = σ_{1} .$
Möbius function:
$\begin{matrix} (2.1.1) & μ (n) = {\begin{cases} 1 & if n = 1 \\ (- 1)^{k} & if n = p_{1} \dots p_{k}, where p_{1}, \dots, p_{k} are distinct primes \\ 0 & if p^{2} ∣ n for some p \end{cases} \end{matrix}$
Liouville function:
$\begin{matrix} (2.1.2) & λ (n) = (- 1)^{a_{1} + \dots + a_{k}} where n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}} \end{matrix}$
(In particular $λ (1) = 1$ as all $a_{i} = 0 .$ )
Von Mangoldt function:
$\begin{matrix} (2.1.3) & Λ (n) = {\begin{cases} \log p & if n = p^{k} for some prime p \\ 0 & if n is not a power of a prime \end{cases} \end{matrix}$
$ω (n) :$ number of distinct prime divisors of $n$
$Ω (n) :$ number of prime divisors of $n$ counted with multiplicity, i.e., $Ω (n) = \sum a_{i}$ where $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}} .$

Observe

λ (n) = (- 1)^{Ω (n)} .

Think of the Von Mangoldt function as a modification of the prime indicator function. The prime indicator function is the function that equals

1

on primes, and

0

on non-primes. The Von Mangoldt function changes the value to

\log p

instead of

1,

and detects powers of primes along with the primes themselves.

Theorem 2.1.2.

For a prime

p

and

k \geq 1,

ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

Proof.

There are

p^{k} / p = p^{k - 1}

multiples of

p

less than or equal to

p^{k};

all other integers in the interval

[1, p^{k}]

are coprime to

p^{k} .

Theorem 2.1.3.

For all

n \geq 1,

\sum_{d ∣ n} ϕ (d) = n .

Proof.

Let

d ∣ n .

\begin{aligned} ϕ (d) & = # {k : 1 \leq k \leq d, (k, d) = 1} \\ = # {k : \frac{n}{d} \leq k \frac{n}{d} \leq n, (k \frac{n}{d}, n) = \frac{n}{d}} \\ = # {m : \frac{n}{d} \leq m \leq n, (m, n) = \frac{n}{d}} \\ = # {m : 1 \leq m \leq n, (m, n) = \frac{n}{d}} . \end{aligned}

So

\begin{aligned} \sum_{d ∣ n} ϕ (d) & = \sum_{d ∣ n} # {m : 1 \leq m \leq n, (m, n) = \frac{n}{d}} \\ = # ⋃_{d ∣ n} {m : 1 \leq m \leq n, (m, n) = \frac{n}{d}} \\ = # {m : 1 \leq m \leq n} \\ = n . \end{aligned}

We used that the union is disjoint. Next, every value

1 \leq m \leq n

has some gcd with

n,

and the gcd must be a divisor of

n .

As

d

runs through the divisors of

n,

so does

n / d .

This shows that the union is equal to the set of

1 \leq m \leq n .

Remark 2.1.4.

Note that the sets

{k : 1 \leq k \leq d, (k, d) = 1}

are not at all disjoint; for example they all contain

1 .

Theorem 2.1.5.

$ϕ (1) = 1$
$ϕ (p) = p - 1$
$ϕ (p^{k}) = p^{k} - p^{k - 1} = p (1 - \frac{1}{p})$
If $(m, n) = 1$ then $ϕ (m n) = ϕ (m) ϕ (n)$
$ϕ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$

Proof.

The first two are left as exercises. The numbers coprime to

p^{k}

are the non-multiples of

p .

There are

p^{k} / p = p^{k - 1}

multiples of

p

in the interval

[1, p^{k}] .

The Chinese Remainder Theorem gives an isomorphism of rings

Z_{m n} ≅ Z_{m} \times Z_{n} .

Among other things, this gives an isomorphism of the groups of units (invertible elements):

Z_{m n}^{\times} ≅ (Z_{m} \times Z_{n})^{\times} ≅ Z_{m}^{\times} \times Z_{n}^{\times} .

(It is left as an exercise that for rings

R, S

in general,

(R \times S)^{\times} ≅ R^{\times} \times S^{\times} .

) Now

# (Z_{m n}^{\times}) = ϕ (m n),

and

# (Z_{m}^{\times} \times Z_{n}^{\times}) = (# Z_{m}^{\times}) \cdot (# Z_{n}^{\times}) = ϕ (m) ϕ (n) .

Finally for

n = \prod p_{i}^{a_{i}}

we have

ϕ (n) = \prod ϕ (p_{i}^{a_{i}}) = \prod p_{i}^{a_{i}} (1 - \frac{1}{p_{i}}) = n \prod (1 - \frac{1}{p_{i}}) .