Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove: When $m > 1$ and $n > 1$ and $\gcd(m, n) > 1$. Then $\phi(mn) \neq \phi(m)\phi(n)$.


Let $m,n \in \mathbb{Z}$ s.t. $\gcd(m,n) > 1$. Consider the congruences:

$x \equiv b \mod m$

$x \equiv c \mod n$

This is where I am stuck. If i were to prove the opposite of this statement I would appeal to the chinese remainder theorem and state that distinct solutions have a correspondence to distinct pairs. So I think is in the same, vein. We do not have a distinct correspondence, so somehow we will end up with: $\phi(mn) \neq \phi(m)\phi(n)$

share|cite|improve this question
When $m$ and $n$ are coprime $\phi(mn) = \phi(m)\phi(n)$ by the Chinese remainder Theorem. – CodeKingPlusPlus Oct 11 '12 at 2:42
@anon It's not always true that $\alpha,\ \beta,\ \gamma$ are pairwise coprime. Consider $(9,\ 12)$. – EuYu Oct 11 '12 at 2:53
@EuYu Silly of me. – anon Oct 11 '12 at 3:08
up vote 1 down vote accepted

Let us use an inductive argument. Suppose that we have $N = mn$. If $N$ is composed of a single prime, say $N=p^k$ partitioned into $m=p^i$ and $n=p^j$ $$\phi(N) = p^k\left(1-\frac{1}{p}\right) > \phi(m)\phi(n) = p^k\left(1-\frac{1}{p}\right)^2$$ The base case holds. Now suppose the inequality holds for all $N$ composed of at most $k$ primes. Consider $$N=p_1^{a_1}\cdots p_{k+1}^{a_{k+1}}$$ Suppose without loss of generality that $N$ is partitioned into $m$ and $n$ where $p_1$ is shared. $$m=p_1^{b_1}\cdot m'$$ $$n=p_1^{c_1}\cdot n'$$ where $a_1 = b_1 + c_1$. Then we have $$\phi(N) = \phi(p_1^{a_1}m'n') = \phi(p_1^{a_1})\phi(m'n')$$ From the inductive hypothesis, $m'$ and $n'$ are composed of $k$ or less primes, therefore $$\phi(m'n')>\phi(m')\phi(n')$$ and we get $$\phi(p_1^{a_1})\phi(m'n')>\left[\phi(p_1^{b_1})\phi(m')\right]\left[\phi(p_1^{c_1})\phi(n')\right] = \phi(m)\phi(n)$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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