What's the proof that the Euler totient function is multiplicative?

Question

That is,

why is $\varphi(AB)=\varphi(A)\varphi(B)$, if $A$ and $B$ are two coprime positive integers?

It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its multiplicativity should be an approximation at most. And why the minimum value for $\varphi (n)$ should be $ \frac{4n}{15} $ completely passes me by.

Answer 1

In general, if $R$ and $S$ are rings, then $R\times S$ is a ring. The units of $R\times S$ are the elements $(r,s)$ with $r$ a unit of $R$ and $s$ a unit of $S$. If $R$ and $S$ are finite rings, the number of units in $R\times S$ is therefore the number of units in $R$ times the number of units in $S$.

Now if $\gcd(A,B)=1$, then $$\mathbb Z/\left<AB\right> \cong \mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$$

This is essentially the Chinese remainder theorem.

But the number of units in the ring $\mathbb Z/\left<n\right>$ is $\phi(n)$. So the number of units in $\mathbb Z/\left<AB\right>$ is $\phi(AB)$ and the number of units in $\mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$ is $\phi(A)\phi(B)$

Answer 2

In general, you're right that $\Phi(AB)\neq\Phi(A)\Phi(B)$--for example, $\Phi(8)=4$, but $\Phi(2)=1$ and $\Phi(4)=2$. At best, we can usually only say that $\Phi(AB)\geq\Phi(A)\Phi(B)$. We will have equality when (and only when) $A,B$ are coprime, though.

Let $R_1,R_2$ be rings, and note that $R_1\times R_2$ is also a ring with componentwise addition and multiplication. A given $(x_1,x_2)\in R_1\times R_2$ has a multiplicative inverse if and only if the $x_k$ have multiplicative inverses in $R_k$.

Note that integers $A,B$ are coprime if and only if there exist integers $X,Y$ such that $AX+BY=1$ if and only if $A$ has a multiplicative inverse modulo $B$ and $B$ has one modulo $A$. Thus, there are precisely $\Phi(A)$ elements of $\Bbb Z/A\Bbb Z$ having multiplicative inverse.

By the above discussion, $\Bbb Z/AB\Bbb Z$ will have $\Phi(AB)$ elements with multiplicative inverses, and $(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$ will have $\Phi(A)\Phi(B)$ such elements.

The only thing left to prove is that there is a bijection (in fact, an isomorphism) between $\Bbb Z/AB\Bbb Z$ and $(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$. That $A,B$ are coprime is crucial to the proof, so be sure you use it! I'd start with the natural homomorphism $\Bbb Z\to(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$ given by $X\mapsto(X\,mod\, A,X\, mod\, B)$, which readily has kernel $AB\Bbb Z$, and then use the coprimality of $A,B$ to show surjectivity, so the desired conclusion follows by First Isomorphism Theorem.

---

Edit: Your addendum is incorrect. The $\frac{4n}{15}$ lower bound is obtained when we're looking at the first $100$ values of $\Phi(n)$--attained by $30,60,90$, but it is misleading. There are numbers beyond it that fall below that bound, such as $210$. There is in fact no lower bounding straight line of positive slope through the origin that applies to all the integers.

Answer 3

If $n=p_1^{a_1}p_2^{a^2} \dots p_r^{a_r}$ with the $p_i$ distinct primes (eg in increasing order to get a canonical form) and the $a_i$ positive integers, then we have:$$\phi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dots\left(1-\frac1{p_r}\right)$$ (worth working out for yourself) - then if $m$ and $n$ are co-prime they bring in different factors for their respective prime divisors and the multiplicativity is easy to see. If you bear in mind that the sum of the reciprocals of primes is unbounded, you will be able to see that you can make the prime bit of the product as small as you like (eg take logs), so that $\frac{\phi(n)}n$ can be made as small as possible. You will even be able to choose values of $n$ which make this fraction particularly small. I mention this expression for $\phi(n)$ because it is the one which has most aided my intuition.

Answer 4

This just addresses the erroneous notion that $\frac{\varphi(n)}n$ has a positive lower bound, but it’s too long for a comment.

If $m_n=p_1\dots p_n$ is the product of the first $n$ primes, then $\varphi(m_n)=\prod\limits_{k=1}^np_k\left(1-\frac1{p_k}\right)$, and $$\frac{\varphi(m_n)}{m_n}=\prod_{k=1}^n\left(1-\frac1{p_k}\right)\;.$$

Consider the reciprocal,

$$\begin{align*} \frac{m_n}{\varphi(m_n)}&=\prod_{k=1}^n\left(\frac1{1-p_k^{-1}}\right)\\ &=\prod_{k=1}^n\sum_{i\ge 0}\frac1{p_k^i}\\ &\ge\prod_{k=1}^n\left(1+\frac1{p_k}\right)\;. \end{align*}$$

For positive $a_k$ the infinite product $\prod_{k\ge 1}(1+a_k)$ converges iff the series $\sum_{k\ge 1}a_k$ converges, and it’s well known that $\sum_{k\ge 1}\frac1{p_k}$ diverges, so $\lim_{n\to\infty}\frac{m_n}{\varphi(m_n)}\to\infty$, and therefore $\lim_{n\to\infty}\frac{\varphi(m_n)}{m_n}=0$.

Answer 5

$$n = \prod_{k=1}^{z}p_{k}^{e_{k}}$$ $$\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ Let $$a=\prod_{k=1}^{w} p_{k}^{e_{k}}\quad b=\prod_{k=w+1}^{z} p_{k}^{e_{k}}$$ $n=ab$, then $$\varphi(a) = a\prod_{k=1}^{w}(1-\frac{1}{p_{k}})$$ $$\varphi(b) = b\prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$$ $$\varphi(a)\varphi(b) = ab\prod_{k=1}^{w}(1-\frac{1}{p_{k}}) \cdot \prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$$ $$=ab\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ $$=n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ $$=\varphi(n)$$ $$\varphi(a)\varphi(b)=\varphi(ab)$$

Answer 6

Möbius inversion can provide a neat proof:

$$ \sum_{d|n}\mu(d)= \begin{cases} 1 & n=1 \\ 0 & n>1 \end{cases} $$

By definition, we have

\begin{aligned} \varphi(n) &=\sum_{\substack{1\le k\le n\\(k,n)=1}}1=\sum_{1\le k\le n}\sum_{d|(k,n)}\mu(d) \\ &=\sum_{d|n}\mu(d)\sum_{\substack{1\le k\le n\\d|k}}1=\sum_{d|n}\mu(d)\frac nd \\ &=n\sum_{d|n}{\mu(d)\over d} \end{aligned}

Since $\mu(d)/d$ is multiplicative w.r.t $d$, it follows from the properties of Dirichlet convolutions that $\varphi(n)$ is also multiplicative.