# help to proof : if a|b then phi(a) | phi(b)

• Nov 26th 2011, 08:58 AM
mostafashaeri
help to proof : if a|b then phi(a) | phi(b)
hello.
can any one proof this problem for me please?
if a|b then phi(a) | phi(b). (b is natural number).

tanx.
• Nov 26th 2011, 09:19 AM
chisigma
Re: help to proof : if a|b then phi(a) | phi(b)
Quote:

Originally Posted by mostafashaeri
hello.
can any one proof this problem for me please?
if a|b then phi(a) | phi(b). (b is natural number).

tanx.

By definition is...

$\varphi(a)= a\ \prod_{p|a} \frac{p-1}{p}$

$\varphi(b)= b\ \prod_{p|b} \frac{p-1}{p}$ (1)

Now if $b|a$ then...

$k= \frac{a}{b}\ \prod_{q} \frac{q-1}{q}$ (2)

... where q belongs to the set of primes deviding a and not b, is a natural number...

Kind regards

$\chi$ $\sigma$
• Nov 26th 2011, 10:17 AM
mostafashaeri
Re: help to proof : if a|b then phi(a) | phi(b)
thank.
So?
i don't understand why b|a?
the problem say that a|b
• Nov 26th 2011, 10:54 AM
mostafashaeri
Re: help to proof : if a|b then phi(a) | phi(b)
i don't understand why b|a . in the problem a|b but you said b|a.
please explain how to continue this proof
thanks
• Nov 26th 2011, 04:59 PM
PaulRS
Re: help to proof : if a|b then phi(a) | phi(b)
Quote:

Originally Posted by mostafashaeri
i don't understand why b|a . in the problem a|b but you said b|a.
please explain how to continue this proof
thanks

I think he switched $a$ and $b$. As for the rest, note that any prime $q$ (from that product in the formula for $k=\frac{\varphi(a)}{\varphi(b)}$) actually divides $\frac{a}{b}$.

Another proof (back to the original $a|b$ ) :

Let $b = c\cdot d$ where $c$ is the greatest integer dividing $b$ such that $\text{gcd}(c,a)=1$.

Adding to this that $a|b$ , we have that $d$ and $a$ must share the exact same prime divisors (and $a|d$ too) . Thus in fact, any number coprime to $d$ is coprime to $a$ and viceversa. It follows then that $\varphi(a) | \varphi(d)$ (*).

Finally since $c$ and $d$ are coprime, we have: $\varphi(b) = \varphi(c)\cdot \varphi (d)$, and since $\varphi(a) | \varphi(d)$ we are done.

$(*)$ In each set $\{k\cdot a,..,k\cdot a +a-1\}$ for $k = 0,...,\tfrac{d}{a}-1$ we have exactly $\varphi(a)$ numbers coprime to $d$. These sets form a partition of $\{0,...,d-1\}$ so indeed $\varphi(a)\cdot \tfrac{d}{a} = \varphi(d)$.