Number theory question about Euler's totient function

363 Views Asked by At

We have two natural numbers, m and n, and m divides n.

Prove, that $\phi(m)$ divides φ(n) too for every m and n.

φ(a) means the Euler's totient function: for an a positive integers, it is the number of lower numbers which are relative prime to a.

For example, φ(4)=2, because only two numbers, 1, and 3 are relative prime to 4.

This question may be a duplicate, but I didn't find any of it yet, if so, I apologise in advance.

2

There are 2 best solutions below

0
On

Write $m = p_1^{a_1}\cdots p_s^{a_s}$ and $m = p_1^{b_1}\cdots p_s^{b_s}\cdots p_r^{b_r}$ ( where $b_i \geq a_i$) and use the multiplicative formula for $\phi$.

0
On

Hint:

If $\;n=p_1^{a_1}\cdot\ldots\cdot p_k^{a_k}\in\Bbb N\;,\;\;p_i\;\;\text{primes}\;,\;\;a_i\in\Bbb N\;$ , then

$$\varphi(n)=n\prod_{i=1}^k\left(1-\frac1{p_i}\right)$$