# Multiplicative Functions

## Arithmetic Functions
:::info
**Definition (Arithmetic Function)**
An *arithmetic function* is a function $f$ defined on the set of positive integers $\mathbb{N}$ (or $\mathbb{Z}^+$) that takes values in the set of complex numbers $\mathbb{C}$.
:::

:::info
**Definition (Multiplicativity)**
An arithmetic function $f$ is classified as:
* **Multiplicative** if $f(mn) = f(m) f(n)$ for all coprime integers $\text{gcd}(m,n)=1$.
* **Completely Multiplicative** if $f(mn) = f(m) f(n)$ for all integers $m,n \in \mathbb{N}$.
:::

:::warning
**Examples**
1. $f(n) = 1$ is completely multiplicative.
2. $g(n) = n$ is completely multiplicative.
:::

:::danger
**Proposition** If $f$ is multiplicative and the prime factorization of $n$ is $n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$, then $f(n)$ can be computed from the values at the prime powers:
$$
f(n) = f(p_1^{a_1}) f(p_2^{a_2}) \cdots f(p_s^{a_s})
$$
:::

## Euler $\varphi$-Function
The **Euler $\varphi$-function** (or Euler's totient function) is a key multiplicative function in number theory.

:::info
**Definition (Euler $\varphi$-Function)**
$$
\varphi(n) := \#\{1 \le a \le n \mid \text{gcd}(a,n)=1\}
$$

This function counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$.
:::

:::danger
**Proposition**
* $\varphi(p) = p - 1$ for a prime $p$.
* $\varphi(p^a) = p^a - p^{a-1}$ for a prime power $p^a$.
* $\varphi(n)$ is a *multiplicative* function.
:::

:::danger
**Theorem (Formula using Prime Factorization)**
If $n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$ is the prime factorization of $n$, then:
\begin{split}
\varphi(n) &= \varphi(p_1^{a_1}) \varphi(p_2^{a_2}) \cdots \varphi(p_s^{a_s}) \\ &= (p_1^{a_1} - p_1^{a_1-1})(p_2^{a_2} - p_2^{a_2-1}) \cdots (p_s^{a_s} - p_s^{a_s-1}) \\ &= n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_s}\right)
\end{split}
:::

:::warning
**Examples**
1. $\varphi(100) = \varphi(2^2)\varphi(5^2) = 100 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 40$.
2. $\varphi(720) = \varphi(2^4)\varphi(3^2)\varphi(5) = 720\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 192$.
:::

:::danger
**Theorem** If $n \ge 3$, then $\varphi(n)$ is an even integer.
:::

:::success
**Exercises**
1. Determine whether each of the following arithmetic functions is completely multiplicative. Prove your answers.
a) $f(n) = 0$
b) $f(n) = 2$
c) $f(n) = n/2$
d) $f(n) = \log n$
e) $f(n) = n^2$
f) $f(n) = n!$
g) $f(n) = n + 1$
h) $f(n) = n^n$
i) $f(n) = \sqrt{n}$
2. Show $\varphi(5186)=\varphi(5187)=\varphi(5188)$.
3. Find all positive integers $n$ such that $\varphi(n) = 6$. Be sure to prove that you have found all solutions.
4. Find all positive integers $n$ such that $\varphi(n) = 24$. Be sure to prove that you have found all solutions.
5. For which positive integers $n$ does $\varphi(3n) = 3\varphi(n)$?
:::

## Summatory Functions and the $\varphi$-Function Identity
:::info
**Definition (Summatory Function)**
If $f$ is an arithmetic function, its summatory function $F$ is defined as the sum of $f$ over all positive divisors $d$ of $n$:
$$
F(n) := \sum_{d \mid n} f(d)
$$
:::

:::warning
**Example**
Let $f(n) = n^2$. The summatory function evaluated at $n=12$ is:
$$
F(12) = \sum_{d \mid 12} d^2 = 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2 = 210
$$
:::

:::danger
**Theorem (Sum over Divisors Identity for $\varphi$)**
For the Euler $\varphi$-function, the summatory function is equal to $n$:
$$
\sum_{d \mid n} \varphi(d) = n \quad \text{for all } n \in \mathbb{N}
$$
:::

:::danger
**Theorem** If $f$ is a multiplicative function, then its summatory function $F(n) = \sum_{d \mid n} f(d)$ is also multiplicative.
:::

## The Sum and Number of Divisors
The $\sigma$ and $\tau$ functions are examples of summatory functions of completely multiplicative functions.

:::info
**Definition**Let $n \in \mathbb{N}$. We define:
* **Sum of Divisors Function**: $\sigma(n) := \sum_{d \mid n} d$
* **Number of Divisors Function**: $\tau(n) := \sum_{d \mid n} 1$
:::

:::danger
**Corollary** Both $\sigma(n)$ and $\tau(n)$ are *multiplicative* functions.
:::

:::danger
**Theorem (Formulas using Prime Factorization)**
If $n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$ is the prime factorization:
* $$\sigma(p^a) = 1 + p + p^2 + \cdots + p^a = \frac{p^{a+1} - 1}{p - 1}, \quad \tau(p^a) = a + 1$$
* $$\sigma(n) = \prod_{i=1}^s \frac{p_i^{a_i + 1} - 1}{p_i - 1}, \quad \tau(n) = \prod_{i=1}^s (a_i + 1)$$
:::

:::warning
**Examples**
1. Let $n=200=2^3\cdot 5^2$.
\begin{split}
\sigma(200) &= \frac{2^{3+1}-1}{2-1} \cdot \frac{5^{2+1}-1}{5-1} = 15 \cdot 31 = 465 \\
\tau(200) &= (3+1)(2+1) = 12
\end{split}
2. Let $n=720=2^4\cdot 3^2\cdot 5^1$.
\begin{split}
\sigma(720) &= \frac{2^5-1}{2-1} \cdot \frac{3^3-1}{3-1} \cdot \frac{5^2-1}{5-1} = 31 \cdot 13 \cdot 6 = 2418 \\
\tau(720) &= (4+1)(2+1)(1+1) = 30
\end{split}
:::

:::success
**Exercises**

6. Find the sum of the positive integer divisors of each of these integers.
a) $35$
b) $196$
c) $1000$
d) $2^{100}$
e) $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11$
f) $2^5 3^4 5^3 7^2 11$
g) $10!$
h) $20!$
7. Which positive integers have an odd number of positive divisors?
8. Find all positive integers $n$ with $\sigma(n)$ equals to each of these integers.
a) $12$
b) $18$
c) $24$
d) $48$
e) $52$
f) $84$
9. Which positive integers have exactly three positive divisors?
:::