Take the 2-minute tour ×

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$.

I was looking for alternative methods to calculate the value of $\phi$ which didn't require the Chinese Remainder Theorem.

I found a very nice proof in "Ireland, Rosen - A Classical Introduction to Modern Number Theory" which use the Moebius function $\mu$ and the Moebius Inversion Formula

I've already proved that $$n= \sum_{d\mid n} \phi(d)$$

and this is the proof I'm speaking about.


the "problem" is the equality $$ n-\sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} \cdots = n(1-(1/p_1))\cdots(1-(1/p_l))$$

I can't handle it very well and so I can't provide a formal proof of its correctness. I tried to reverse the reasoning and to show that the right side is equal to the left side and then reverse again the reasoning, but I'm submersed with products…

PLEASE NOTE I need a proof / reasoning which doesn't use the right side of the equality, in other words I need something which start with something like this $$ n-\sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} \cdots = \ ? $$ ("?" indicates that I don't know what could be the result) and shows how to manipulate the factors to obtain the right side

share|improve this question
Have you already seen Euler's argument for $\varphi$ being multiplicative? –  Ian Mar 15 '14 at 18:07
The $n$ doesn't matter. The expansion of $(1-x_1)(1-x_2)\cdots(1-x_k)$ is clear. True, this uses the right side. If we want to use the left side only, it is a matter of recognizing something familiar. –  André Nicolas Mar 15 '14 at 18:07
@IanMateus $\varphi(mn)=\varphi(m)\varphi(n)$ if $(m,n)=1$? I don't think I'll need that here. –  Riccardo Mar 15 '14 at 18:08
This is actually crucial because it is not hard to show $\varphi(p^k)=p^k(1-p^{-1})$ for $p$ prime. Combine this with FTA and you are set. You can see Euler's proof here. –  Ian Mar 15 '14 at 18:10
@IanMateus yeah, but I wanted to follow this reasoning, I spoke about alternative proofs of the properties of totient function, and I've already seen the proof you are describing :) anyway thanks!:) –  Riccardo Mar 15 '14 at 18:12

2 Answers 2

up vote 1 down vote accepted

Hint: Think of Vieta formulas (sums), where $\frac{1}{p_i}$ are the "roots". Then set $X=1$.

Vieta: $$X^m - \left(\sum_{i=1}^mx_i\right)X^{m-1} + \left(\sum_{1\leq i<j\leq m}x_ix_j\right)X^{m-2}-\ldots = (X-x_1)(X-x_2)\ldots (X-x_m).$$

share|improve this answer
so it's a matter of view the "Vieta's formulas" hiding in the sums? –  Riccardo Mar 15 '14 at 18:39
Yes. Vieta is doing basically what Andre Nicolas is suggesting but with an indeterminate $X$ instead of $1$. Basically, you are adding Vieta SUMS on the left hand side. –  ir7 Mar 15 '14 at 18:44

You can show it using a combinatorial argument: the nasty sums come from the inclusion-exclusion principle and the product comes from the multiplication principle.

Consider the set $S=\{1,2,\ldots, n\}$ and $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$. Let $A_{r}\subset S$ be the set of numbers $\in S$ divisible by at least $r$ primes in the factorization of $n$. Note (show) that $$|A_{r}|=\sum_{i_1\lt i_2 \lt \ldots \lt i_r}\left\lfloor\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_r}}\right\rfloor=\sum_{i_1\lt i_2 \lt \ldots \lt i_r}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_r}}.$$

How many numbers are coprime to $n$? We will find it using two ways. First, compute all numbers with some common factor to $n$. By the inclusion-exclusion principle, there are exactly

$$n-\varphi(n)=|A_{1}|-|A_{2}|\pm\cdots=\sum_i\frac{n}{p_i}-\sum_{i\lt j}\frac{n}{p_ip_j}\pm\cdots$$

On the other hand, we can compute it in other way. There are $n/p_1$ numbers divisible by $p_1$ and thus $n(1-p_1^{-1})$ numbers coprime to $p_1$. By a similar argument, there are $n(1-p_1^{-1})(1-p_2^{-1})$ numbers coprime to both $p_1$ and $p_2$. Repeating this yields $$\varphi(n)=n-\sum_i\frac{n}{p_i}+\sum_{i\lt j}\frac{n}{p_ip_j}\mp\cdots=n(1-p_1^{-1})(1-p_2^{-1})\cdots$$

share|improve this answer
Seems a very interesting proof, but I didn't understand what kind of sets you are considering to apply the inclusion-exclusion principle. So, can can you expand a little that passage? –  Riccardo Mar 15 '14 at 18:57
@RicPed the first sum is $\sum n/p_i$, with $p_i\mid n$. It represents the number of divisibles by $p_1, p_2,\ldots$. The second sum is the number of divisibles by $p_1p_2, p_2p_3, \ldots$ and so on. It should be $\lfloor n/p_ip_jp_k\cdots\rfloor$ originally, but as $n$ is divisible by them, it is a integer, so we can drop the floors. –  Ian Mar 15 '14 at 19:10
@RicPed I edited the answer to make the sets explicit. –  Ian Mar 15 '14 at 20:41
Thanks, I'll read it now:) –  Riccardo Mar 15 '14 at 21:02

Your Answer


