0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @fleablood $\phi$ is multiplicative but not completely multiplicative: $\phi(kn) = \phi(k) \phi(n)$ if $k$ and $n$ are coprime, but generally not otherwise. $\endgroup$ Dec 12 '16 at 5:50
  • $\begingroup$ Consider phi ($\prod p_i^{n_i})=\prod p_i (p^{n-1}-1) $ find when $\prod etc= phi (nk)=n\prod etc $ $\endgroup$
    – fleablood
    Dec 12 '16 at 5:58
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.