Prove that $\phi(mn) = m \phi(n) \Rightarrow m \mid n$

590 Views Asked by At

Questions:

$m,n \in \mathbb{Z^{+}}$

(1) Prove that $ m \mid n \Rightarrow \phi(mn) = m \phi(n) $

(2) Prove that $\phi(mn) = m \phi(n) \Rightarrow m \mid n$

I am exclusively unsure about my answer for (2), but including my answer for (1) for context. (1) has been discussed before on this website, but not (2), so I argue that this is therefore not a duplicate question.

Attempted solutions:

(1)

First, let us write out the prime factors of $m$ and $n$.

$$m = \prod^k_{i = 1} p_i^{\alpha_i}$$

$$n = \prod^s_{i = 1} p_i^{\beta_i}$$

where $\alpha_i \leq \beta_i$ and $k \geq s$

Their product then becomes:

$$mn = \prod^s_{i = 1} p_i^{\alpha_i \cdot \beta_i}$$

Applying Euler's phi function on this product:

$$\phi(mn) = mn \cdot \prod^s_{i = 1} \frac{p_i - 1}{p_i}$$

Applying Euler's phi function on $n$:

$$\phi(n) = n \cdot \prod^s_{i = 1} \frac{p_i - 1}{p_i}$$

This then trivially implies:

$$\phi(mn) = m \phi(n)$$

$$\tag*{$\blacksquare$}$$

(2)

From the definition of $\phi(mn) = m \phi(n)$, we have:

$$\phi(mn) = mn \cdot \prod^s_{i = 1} \frac{p_i - 1}{p_i}$$ $$\phi(n) = n \cdot \prod^s_{i = 1} \frac{p_i - 1}{p_i}$$

Not really sure how to proceed from here. I know that I should more or less run the previous proof "in reverse", but unsure about the specifics.

One idea I had was to write out the prime factors of $m$ and $n$.

$$m = \prod^k_{i = 1} p_i^{\alpha_i}$$

$$n = \prod^s_{i = 1} p_i^{\beta_i}$$

and then conclude that all prime factors in m are in n and no prime factors in $n$ are not in $m$ (and that $\beta_i$ is larger than $\alpha_i$) and therefore that $m \mid n$.

This, however, seems a bit insufficiently rigorous. What is the proper way to finish this off?