2
$\begingroup$

I wanted to prove that $\varphi$ is multiplicative (that for $(a,b)=1$, $\varphi(ab)=\varphi(a)\varphi(b)$) using the following idea:

  • Define $\varphi'$ by $n = \varphi'(n) + \varphi(n)$.
  • Multiply out $\varphi(a)\varphi(b) = (a - \varphi'(a))(b - \varphi'(b)) = ab - \varphi'(a)b - a \varphi'(b) + \varphi'(a)\varphi'(b)$
  • Use the principle of inclusion exclusion ($|A \cup B| = |A| + |B| - |A \cap B|$).

but I could not get it to work out.

Is this approach possible at all? How can it be saved?


So I just need to construct sets $A(a,b)$ and $B(a,b)$ that satisfy the following

$\begin{matrix} \varphi'(ab) &=& \varphi'(a) b &+& a \varphi'(b) &-& \varphi'(a)\varphi'(b)\\ || & & || & & || & & || \\ |A \cup B| &=& |A| &+& |B| &-& |A \cap B| \end{matrix}$

then the proof follows from simple algebra. I just cannot find any way to construct such sets - since the identity is true I imagine they do exist but I am not be completely sure especially since I couldn't construct them.

  • 0
    @muad: In regular LaTeX you can use a `\rotatebox` command, but I do not know if the interpret supports it here.2010-10-16

1 Answers 1

4

Oh, I see. In $\mathbb{Z}/(ab)\mathbb{Z}$ let $A$ be the set of elements not relatively prime to $a$ and let $B$ be the set of elements not relatively prime to $b$. From here what you want follows by the Chinese Remainder Theorem. (Of course, you could just use CRT from the get-go.)