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

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

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

Now if $\displaystyle b|a$ then...

$\displaystyle 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

$\displaystyle \chi$ $\displaystyle \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 $\displaystyle a$ and $\displaystyle b$. As for the rest, note that any prime $\displaystyle q$ (from that product in the formula for $\displaystyle k=\frac{\varphi(a)}{\varphi(b)}$) actually divides $\displaystyle \frac{a}{b}$.

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

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

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

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

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