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

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)$

• Why use the abstract algebra tag rather than the number theory tag? Jan 11, 2014 at 15:06
• this problem is from abstract algebra class :D Jan 11, 2014 at 15:10

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.

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.

• See here for a proof of Lemma 2 $\$ Jun 12, 2016 at 15:58

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).$$

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.

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

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).

• can you explain a little more, I still can't see how this can help me prove that statement. Jan 11, 2014 at 15:55