Prove that if $d$ divides $n$ then $φ(d)$ divide $φ(n)$ for $φ$ denotes Euler’s φ-function.

Question

Prove that if $d$ divides $n$ then $φ(d)$ divide $φ(n)$ for $φ$ denotes Euler’s $φ$-function.

I know that $d|n$ mean there exists some integer $k$ such that $n=kd$, but how can I use this to prove $φ(d)$ divide $φ(n)$

Answer 1

It is true for $\rm\color{#0a0}{prime\ powers}$, so for all naturals, because $\phi$ is $\color{#c00}{\rm multiplicative},$ i.e. $\,\phi(ab) = \phi(a)\phi(b)\,$ for coprime $a,b,\,$ therefore $\ \phi(p_1^{n_1}\cdots p_k^{n_k}) = \phi(p_1^{n_1})\cdots \phi(p_k^{n_k})\,$ for distinct primes $\,p_i$. Explicitly

$$\begin{eqnarray} &&\qquad\qquad\qquad\ \ \ p^i \cdots q^j\ \mid\ p^I\cdots q^J\quad\ {\rm for\ distinct\ primes}\ \ p,\ldots, q \\ \Rightarrow\ &&\qquad \quad\ \ \color{#0a0}{p^i\mid p^I},\qquad\quad\ \ldots,\qquad\quad \ \ q^j\mid q^J \\ \Rightarrow\ &&\color{#0a0}{(p\!-\!1)p^{i-1}\mid (p\!-\!1)p^{I-1}},\ldots,(q\!-\!1)q^{j-1}\mid (q\!-\!1)q^{J-1} \\ \Rightarrow\ &&\qquad\ \color{#0a0}{\phi(p^i)\mid \phi(p^I)},\qquad\ldots,\qquad\,\phi(q^j)\mid\phi(q^J)\\ \Rightarrow\ &&\qquad\qquad\ \, \phi(p^i)\cdots\phi(q^j)\mid \phi(p^I)\cdots\phi(q^J)\\ \Rightarrow\ &&\qquad\qquad\qquad\!\phi(p^i\cdots q^j)\mid \phi(p^I\cdots q^J)\quad\ \ \rm by\ \phi\ is\ \color{#c00}{multiplicative} \end{eqnarray}$$

Remark $\,\ $ Similarly, generally a "multiplicative" statement about a multiplicative function is true if it is true for prime powers.

Answer 2

Lemma1: $\phi(n)=n\prod_{p|n}(1-1/p)$

Lemma2: $\phi(mn)=\phi(m)\phi(n)\dfrac{d}{\phi(d)}$, where $d=(m,n)$. (Deduced from Lemma 1)

Since $a|b$ we have $b=ac$ where $1 \leq c \leq b$. If $c=b$ then $a=1$ and $\phi(a)|\phi(b)$ is trivially satisfied. Therefore, assume $c<b$. From Lemma2 we have $\phi(b)=\phi(ac)=\phi(a)\phi(c)\dfrac{d}{\phi(d)}=d\phi(a)\dfrac{\phi(c)}{\phi(d)}(*)$

where $d=(a,c)$. Now the result follows by induction on $b$. For $b=1$ it holds trivially. Suppose, then, it holds for all integers $<b$. Then it holds for $c$ so $\phi(d)|\phi(c)$ since $d|c$. Hence the right member of (*) is a multiple of $\phi(a)$ which means $\phi(a)|\phi(b)$. This proves the assertion.

Answer 3

You can use the formula $$ \text{If } n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}\Rightarrow \phi(n)=p_1^{a_1-1}p_2^{a_2-1}\cdots p_r^{a_r-1} \left(p_1-1\right) \left(p_2-1\right)\cdots\left(p_r-1\right). $$

Answer 4

Since another question asked this question for the case that $d$ is a prime$~p$, and it was closed as a duplicate of this one before I could post my answer, I'll post that answer here, admitting that it only deals with a special case; on the other hand I imposed myself an addition restriction.

I'll add that the method below can in principle be extended to the case of an arbitrary divisor $d$ of $n$ instead of a prime divisor$~p$, still essentially by reducing to showing the fibres of the reduction $\def\Z{\Bbb Z} \def\r#1{\Z/#1\Z} \def\m#1{(\r{#1})^\times} \m{n}\to\m{d}$ are all non-empty, which can be done by lifting first in any way to the maximal divisor of$~n$ with the same prime factors as$~d$, and then using the Chinese remainder theorem to lift from there to$~n$. But this requires a bit more effort (and more Chinese remaindering) which I'll leave as an exercise.

---

Just as a challenge, I'll try to see if I can formulate a proof of without using the explicit formula for $\phi(n)$.

From $p\mid n$ we get the existence of a ring morphism $\r{n}\to\r{p}$, which maps invertible elements to invertible elements. So if we define $r:\m{n}\to\m{p}$ to be the restriction of that ring morphism to the respective groups of invertible elements (which are of sizes $\varphi(n)$ respectively $\varphi(p)=p-1$), our divisibility $p-1\mid\varphi(n)$ will be assured if we can show that all fibres of $r$ above any $~u\in\m{p}$ (which are the sets $r^{-1}(\{u\})=\{\, x\in\m{n}\mid r(x)=u\,\}$) all have the same size.

To this end I first show that each fibre is non-empty: we can lift any$~u\in\r{p}^\times$ to an $x\in\r{n}^\times$. Setting $q=p^k$ for the largest $k\in\Bbb N$ for which $p^k$ divides $n$, we shall first lift $u$ to$~\m{q}$, and invertible class modulo$~q$. Indeed any representative $\tilde u\in\Bbb Z$ of $u$ gives rise to such and invertible class since a Bézout relation $\gcd(\tilde u,q)=1=s\tilde u+tq$ provides an inverse$~s$ of$~\tilde u$ modulo$~q$. Next for $m=n/q$, so that $\gcd(q,m)=1$, the Chinese remainder theorem says that the congruences $x\equiv\tilde u\pmod q$ and $x\equiv1\pmod m$ admits a common solution, whose image in$~\r{n}$ is invertible (a common solution of similar congruences with $s$ in place of$~\tilde u$ gives an inverse) and provides our lift of$~u$.

Now to show that all fibres of $r:\m{n}\to\m{p}$ have the same number of elements, it suffices to observe that for any fibre $F=r^{-1}(\{u\})$ and any $x\in F$, multiplication by$~x$ provides a bijection $r^{-1}(\{1\})\to F$ (since multiplication by the inverse of $x$ in $\m{n}$ gives the inverse map), so that all fibres have the same number of elements as the fibre $r^{-1}(\{1\})$, QED.

Answer 5

Hint: Use that if $p$ and $q$ are primes you have $$ \varphi(p\cdot q) = \varphi(p)\cdot \varphi(q) $$

Answer 6

You may know that $\phi(pd)=p\phi(d)$ and $\phi(pd)=(p-1)\phi(d)$ if $p\not\mid d$ (where $p$ is a prime).