Find some $n, k$ such that: $\phi(kn) = k * \phi(n)$

465 Views Asked by At

This question might be a duplicate.

For what positive integers $n$, $k$ is $\phi(kn) = k \cdot \phi(n)$?

I read Wikipedia page but I did not find any identity to help me answer the question so I tried some examples that given identity works:

$$k = 1, n = 1\\ k = 2, n = 2\\ k = 3, n = 3\\ k = 4, n = 4\\ k = 5, n = 5\\ k = 6, n = 6\\ k = 7, n = 7\\ k = 9, n = 9\\ k = 10, n = 10$$

Any hint would be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

The condition is that every prime dividing $k$ divides $n$. To see this, let $k = k_1 k_2$ and $n = n_1 n_2$ where $k_1$ and $n_1$ are divisible by the same set $S$ of primes, while $k_2$ and $n_2$ are coprime to each other and to $k_1$ and $n_1$. Thus we have $$ \frac{\varphi(k n)}{k \varphi(n)} = \frac{\varphi(k_1 n_1) \varphi(k_2) \varphi(n_2)}{k_1 k_2 \varphi(n_1) \varphi(n_2)} = \frac{\varphi(k_1 n_1) \varphi(k_2) }{k_1 k_2 \varphi(n_1) } $$ But if $k_1 = \prod_{p \in S} p^{d(p)}$ and $n_1 = \prod_{p \in S} p^{e(p)}$, where $d(p) \ge 1$ and $e(p) \ge 1$, we have $$ \frac{\varphi(k_1 n_1)}{k_1 \varphi(n_1)} = \prod_{p \in S} \frac{(p-1) p^{e(p)+d(p)-1}}{p^{d(p)}(p-1)p^{e(p)-1}} = 1$$ So the condition reduces to $ \varphi(k_2) = k_2$, and this is only true for $k_2 = 1$.