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