Multiplicative Functions

Definition 2.2 (Multiplicative Function)   A function $f:\mathbb{N}\rightarrow \mathbb{Z}$ is multiplicative if, whenever $m, n\in\mathbb{N}$ and $\gcd(m,n)=1$ , we have

$$f(mn) = f(m)\cdot f(n).$$

Recall from Definition 2.1.17 that the Euler $\varphi$ -function is

$$\varphi (n) = \char93 \{a : 1\leq a \leq n$$ and $$\gcd(a,n)=1\}.$$

Lemma 2.2   Suppose that $m, n\in\mathbb{N}$ and $\gcd(m,n)=1$ . Then the map

$$\psi: (\mathbb{Z}/mn\mathbb{Z}{})^* \rightarrow (\mathbb{Z}/m\mathbb{Z}{})^* \times (\mathbb{Z}/n\mathbb{Z}{})^*.$$ (2.2.1)

defined by

$$\psi(c) = (c$$ mod $$m, c$$    mod $$n)$$

is a bijection.

Proof. We first show that $\psi$ is injective. If $\psi(c)=\psi(c')$ , then $m\mid c-c'$ and $n\mid c-c'$ , so $nm\mid c-c'$ because $\gcd(n,m)=1$ . Thus $c=c'$ as elements of $(\mathbb{Z}/mn\mathbb{Z}{})^*$ .

Next we show that $\psi$ is surjective, i.e., that every element of $(\mathbb{Z}/m\mathbb{Z}{})^* \times (\mathbb{Z}/n\mathbb{Z}{})^*$ is of the form $\psi(c)$ for some $c$ . Given $a$ and $b$ with $\gcd(a,m)=1$ and $\gcd(b,n)=1$ , Theorem 2.2.2 implies that there exists $c$ with $c\equiv a\pmod{m}$ and $c\equiv b\pmod{n}$ . We may assume that $1\leq c\leq nm$ , and since $\gcd(a,m)=1$ and $\gcd(b,n)=1$ , we must have $\gcd(c,nm)=1$ . Thus $\psi(c)=(a,b)$ . $\qedsymbol$

Proposition 2.2 (Multiplicativity of $\varphi$ )   The function $\varphi$ is multiplicative.

Proof. The map $\psi$ of Lemma 2.2.6 is a bijection, so the set on the left in (2.2.1) has the same size as the product set on the right in (2.2.1). Thus

$$\varphi (mn) = \varphi (m)\cdot \varphi (n).$$

$\qedsymbol$

The proposition is helpful in computing $\varphi (n)$ , at least if we assume we can compute the factorization of $n$ (see Section 3.3.1 for a connection between factoring $n$ and computing $\varphi (n)$ ). For example,

$$\varphi (12) = \varphi (2^2)\cdot \varphi (3) = 2\cdot 2 = 4.$$

Also, for $n\geq 1$ , we have

$$\varphi (p^n) = p^n - \frac{p^n}{p} = p^n - p^{n-1} = p^{n-1}(p-1),$$ (2.2.2)

since $\varphi (p^n)$ is the number of numbers less than $p^n$ minus the number of those that are divisible by $p$ . Thus, e.g.,

$$\varphi (389\cdot 11^2) = 388 \cdot (11^2 - 11) = 388\cdot 110 = 42680.$$