Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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.

share|cite|improve this question
Chandru1: Euler's totient function, the size of the set of numbers coprime and below the argument. It can also be considered the size of multiplicative group $(\mathbb Z/n\mathbb Z)^\times$ (which gives a very direct proof). – anon Oct 15 '10 at 20:10
Where is $\varphi$ defined ($\mathbb{Z}$?) and where is it's value ($\mathbb{C}$)? – AD. Oct 15 '10 at 20:22
AD. $\varphi : \mathbb N \rightarrow \mathbb N$ – anon Oct 15 '10 at 20:30
I don't understand why this would be useful. For one thing, you aren't using any properties of the totient. – Qiaochu Yuan Oct 15 '10 at 21:33
@Qiaochu Yuan, It is very possible that my attempt is just mislead - I'm not sure how I could ascertain that myself though. Also I updated the question to pinpoint one thing, which if resolved, would let the result follow. – anon Oct 16 '10 at 14:53
up vote 4 down vote accepted

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

share|cite|improve this answer

Your Answer


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