Take the 2-minute tour ×

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

1 Answer 1

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|improve this answer

Your Answer


