5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why use the abstract algebra tag rather than the number theory tag? $\endgroup$ – Ayesha Jan 11 '14 at 15:06
  • $\begingroup$ this problem is from abstract algebra class :D $\endgroup$ – Diane Vanderwaif Jan 11 '14 at 15:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See here for a proof of Lemma 2 $\ $ $\endgroup$ – Bill Dubuque Jun 12 '16 at 15:58
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ can you explain a little more, I still can't see how this can help me prove that statement. $\endgroup$ – Diane Vanderwaif Jan 11 '14 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.