The problem:

(I will presume that d and n are positive integers.) This is one of those "duh!" thoughts but I am messing up the proof somehow. I'd appreciate it is someone could take a look at it.Prove that if d divides n then $\displaystyle \phi (d) $ divides $\displaystyle \phi (n) $.

First: If d|n then n = kd for some positive integer k. Using their decomposition into powers of primes, let

$\displaystyle d = 2^{a_2} \cdot 3^{a_3} \cdot 5^{a_5} \cdot \text{ ...}$

and

$\displaystyle k = 2^{b_2} \cdot 3^{b_3} \cdot 5^{b_5} \cdot \text{ ...}$

Then

$\displaystyle kd = 2^{a_2 + b_2} \cdot 3^{a_3 + b_3} \cdot 5^{a_5 + b_5} \cdot \text{ ...}$

Now, we have that

$\displaystyle \phi (d) = \left ( 2^{a_2 -1 } \right ) (2 - 1) \cdot \left ( 3^{a_3 -1 } \right ) (3 - 1) \cdot \left ( 5^{a_5 -1 } \right ) (5 - 1) \cdot \text{ ...}$

and

$\displaystyle \phi (kd) = \left ( 2^{a_2 + b_2 -1 } \right ) (2 - 1) \cdot \left ( 3^{a_3 + b_3 - 1 } \right ) (3 - 1) \cdot \left ( 5^{a_5 + b_5 - 1 } \right ) (5 - 1)\cdot \text{ ...}$

So finally we get

$\displaystyle \frac{ \phi (kd) }{ \phi (d) } = \left ( 2^{(a_2 + b_2 - 1) - (a_2 - 1)} \right ) \cdot \left ( 3^{(a_3 + b_3 - 1) - (a_3 - 1)} \right ) \cdot \text{ ...}$

$\displaystyle \frac{ \phi (kd) }{ \phi (d) } = \left ( 2^{b_2} \right ) \cdot \left ( 3^{b_3} \right ) \cdot \left ( 5^{b_5} \right ) \cdot \text{ ...}$

or

$\displaystyle \frac{ \phi (kd) }{ \phi (d) } = k$

Now, I thought that simplified expression to be kinda cool. But as I was thinking about it I checked:

$\displaystyle \frac { \phi (3 \cdot 4) }{ \phi (3) } = \frac{4}{2} = 2 \neq k$

So I've done something incorrectly. (Though I suspect the general structure of the proof is sound.)

Any thoughts?

-Dan