5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ If you let $m=12$ and $n=6$, then $\phi(mn)=\phi(72)=24$ and $m \phi(n)=12\phi(6)=24$, but 12 does not divide 6. $\endgroup$ – user84413 Oct 4 '15 at 21:17
  • $\begingroup$ @user84413 so in essence you are telling me that (2) is actually false, per your counterexample? $\endgroup$ – MathInferno Oct 4 '15 at 21:23
  • 1
    $\begingroup$ Yes, I think so -- all you can conclude, using the same type of argument you used for (1), is that every prime factor of m is a prime factor of n. You can also use m=4, n=6. $\endgroup$ – user84413 Oct 4 '15 at 21:24

Your Answer

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

Browse other questions tagged or ask your own question.