1
$\begingroup$

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

Proof

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

  • 0
    When $m$ and $n$ are coprime $\phi(mn) = \phi(m)\phi(n)$ by the Chinese remainder Theorem.2012-10-11
  • 0
    @anon It's not always true that $\alpha,\ \beta,\ \gamma$ are pairwise coprime. Consider $(9,\ 12)$.2012-10-11
  • 0
    @EuYu Silly of me.2012-10-11

1 Answers 1

1

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