Multiplicativity of the Totient Function

($\Rightarrow$) Suppose $\gcd(k,mn)=1$. If a prime $p$ divided both $k$ and $m$, then $p$ would divide $k$ and $mn$, contradicting $\gcd(k,mn)=1$. So $\gcd(k,m)=1$; symmetrically $\gcd(k,n)=1$. ($\Leftarrow$) Suppose $\gcd(k,m)=1$ and $\gcd(k,n)=1$. Suppose toward contradiction that some prime $p$ divides both $k$ and $mn$. Since $p$ is prime and $p\mid mn$, $p\mid m$ or $p\mid n$ (Euclid's lemma). If $p \mid m$, then $p$ divides both $k$ and $m$, contradicting $\gcd(k,m)=1$. If $p\mid n$, similarly contradicting $\gcd(k,n)=1$. Hence no common prime factor exists, so $\gcd(k,mn)=1$. $\blacksquare$

Proof of (a): Multiplicativity, via the Chinese Remainder Theorem. Let $m,n$ be positive integers with $\gcd(m,n)=1$. We construct an explicit bijection

via $\Phi(k) = (k \bmod m,\, k \bmod n)$ (representing residues in the range $1,\dots,m$ and $1,\dots,n$ respectively, using $m$ in place of $0$ and $n$ in place of $0$ for the residue that is $\equiv 0$). $\Phi$ is well-defined and injective. By the Chinese Remainder Theorem, since $\gcd(m,n)=1$, for every pair of residues $(r,s)$ with $0\le r<m$, $0\le s<n$, there is a unique residue class $k \pmod{mn}$ with $k\equiv r\pmod m$ and $k\equiv s\pmod n$. Restricting $k$ to representatives $\{1,\dots,mn\}$ (one representative per residue class mod $mn$), this uniqueness says exactly that $\Phi$ is injective on $\{1,\dots,mn\}$: distinct $k, k'$ in this range with the same $(k\bmod m, k\bmod n)$ would both solve the same CRT system, forcing $k\equiv k'\pmod{mn}$, hence $k=k'$ since both lie in $\{1,\dots,mn\}$. $\Phi$ is surjective. Given any $(r,s) \in \{1,\dots,m\}\times\{1,\dots,n\}$ (again reading residue $m$ as "$0 \bmod m$" and residue $n$ as "$0 \bmod n$"), CRT guarantees existence of $k$ with $k\equiv r \pmod m$, $k \equiv s\pmod n$; taking the representative of this class lying in $\{1,\dots,mn\}$ gives a preimage. Since $|\{1,\dots,mn\}| = mn = |\{1,\dots,m\}\times\{1,\dots,n\}|$, an injective map between finite sets of equal size is automatically a bijection; the surjectivity argument above confirms this directly as well. $\Phi$ respects coprimality. By the Coprimality to a product, for $k\in\{1,\dots,mn\}$,

Writing $r = \Phi(k)_1 \in \{1,\dots,m\}$ and $s=\Phi(k)_2\in\{1,\dots,n\}$, since $k \equiv r \pmod m$ we have $\gcd(k,m) = \gcd(r,m)$ (gcd depends only on residue class), and similarly $\gcd(k,n)=\gcd(s,n)$. Hence

Therefore $\Phi$ restricts to a bijection between

and

(Restriction of a bijection to a subset that maps exactly onto a subset of the target is itself a bijection between those subsets — this is immediate from the definitions of injectivity/surjectivity applied to the smaller sets.) Taking cardinalities: $|A| = \varphi(mn)$ by definition, and $|B| = \varphi(m)\cdot\varphi(n)$ since $B$ is a Cartesian product of two finite sets. Hence

This completes the proof of (a). $\blacksquare$

Proof of (b): the value on a prime power. Fix a prime $p$ and $a \geq 1$. Among the integers $1,2,\dots,p^a$, an integer $k$ satisfies $\gcd(k,p^a) > 1$ if and only if $p \mid k$ (since the only prime factor of $p^a$ is $p$). The multiples of $p$ in $\{1,\dots,p^a\}$ are exactly

of which there are precisely $p^{a-1}$ (they are $p\cdot j$ for $j=1,\dots,p^{a-1}$). Hence the number of integers in $\{1,\dots,p^a\}$ not divisible by $p$ — equivalently coprime to $p^a$ — is

This proves (b). $\blacksquare$

Proof of (c): the product formula, by induction using (a) and (b). Let $n = p_1^{a_1}\cdots p_k^{a_k}$ with distinct primes $p_1,\dots,p_k$ and $a_i \geq 1$. We induct on $k$, the number of distinct prime factors. Base case $k=1$: $n = p_1^{a_1}$, and by (b), $\varphi(n) = n(1-1/p_1)$, matching the formula in (c) with a single factor. Inductive step: Suppose the formula holds whenever $n$ has fewer than $k$ distinct prime factors ($k\ge 2$). Write $n = p_1^{a_1}\cdots p_{k-1}^{a_{k-1}} \cdot p_k^{a_k} =: M \cdot p_k^{a_k}$, where $M = p_1^{a_1}\cdots p_{k-1}^{a_{k-1}}$ has $k-1$ distinct prime factors. Since $p_k$ does not divide $M$ (the $p_i$ are distinct primes and $M$'s only prime factors are $p_1,\dots,p_{k-1}$), we have $\gcd(M, p_k^{a_k}) = 1$. By part (a),

By the inductive hypothesis applied to $M$,

By (b),

Multiplying, and using $n = M\cdot p_k^{a_k}$:

This completes the induction, establishing (c) for all $n>1$. (For $n=1$ the product formula is vacuous/trivial, consistent with $\varphi(1)=1$.) Finally, expanding each factor: $n\left(1-\frac1{p_i}\right)$ contributes, over the whole factorization, exactly

since $n = \prod p_i^{a_i}$ and multiplying by $(1-1/p_i)$ for each $i$ reduces one power of $p_i$ and multiplies by $(p_i - 1)$. $\blacksquare$