## The Euler totient function is monotone with respect to divisibility

Prove that if $d$ divides $n$, then $\varphi(d)$ divides $\varphi(n)$, where $\varphi$ denotes Euler’s totient function.

First, note that the theorem is trivial for $n = 1,0,-1$. In the remainder we will assume that $n$ is not one of these.

By the Fundamental Theorem of Arithmetic, every integer $n$ can be expressed as a finite and nonempty product of primes $n = p_1^{a_1} \ldots p_k^{a_k}$ in a unique way (up to order). We will call the number $k$ of distinct prime factors of $n$ the length of $n$.

Let $n$ and $d$ be integers such that $d|n$. We wish to show that $\varphi(d)|\varphi(n)$; we will proceed by induction on the length of $n$.

For the base case, note that if $n$ has length 1 then $n = p^t$ for some nonnegative integer $t$. Moreover, since $d|n$ we have $d = p^s$ for some nonnegative integer $s$ with $s \leq t$. Then $\varphi(n) = p^{t-1}(p-1) = p^{t-s} p^{s-1}(p-1) = p^{t-s} \varphi(d)$, so that $\varphi(d)|\varphi(n)$.

Suppose now that the proposition is true for all integers of length $\ell$, and let $n$ be an integer of length $\ell + 1$. Then we may factor $n$ as $n = p^t m$ where $p$ is a prime not dividing $m$ and $m$ has length $\ell$. Now if $d|n$, we may factor $d$ as $d = p^s m^\prime$ for some $s \leq t$ and $m^\prime$ dividing $m$. Since $m$ has length $\ell$, we have $\varphi(m) = h \varphi(m^\prime)$ for some h. Thus

 $\varphi(n)$ = $\varphi(p^t) \varphi(m)$ = $p^{t-1}(p-1) h \varphi(m^\prime)$ = $p^{t-s} h \varphi(d)$,

so that $\varphi(d)|\varphi(n)$. By induction, for all integers $n$ we have that if $d|n$ then $\varphi(d)|\varphi(n)$. $\blacksquare$