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.

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ enter image description here

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

  • $\begingroup$ Have you already seen Euler's argument for $\varphi$ being multiplicative? $\endgroup$ – Ian Mateus Mar 15 '14 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Mar 15 '14 at 18:07
  • $\begingroup$ @IanMateus $\varphi(mn)=\varphi(m)\varphi(n)$ if $(m,n)=1$? I don't think I'll need that here. $\endgroup$ – Riccardo Mar 15 '14 at 18:08
  • $\begingroup$ 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. $\endgroup$ – Ian Mateus Mar 15 '14 at 18:10
  • 1
    $\begingroup$ The familiar thing is recalled well by ir7 below. It we really feel like it, we can prove the result easily by induction. Look at the effect of multiplying $(1-x_1)\cdots(1-x_k)$, as expanded on the left, by $1-x_{k+1}$. $\endgroup$ – André Nicolas Mar 15 '14 at 19:14

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

  • $\begingroup$ so it's a matter of view the "Vieta's formulas" hiding in the sums? $\endgroup$ – Riccardo Mar 15 '14 at 18:39
  • $\begingroup$ 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. $\endgroup$ – 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$$

  • $\begingroup$ 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? $\endgroup$ – Riccardo Mar 15 '14 at 18:57
  • 1
    $\begingroup$ @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. $\endgroup$ – Ian Mateus Mar 15 '14 at 19:10
  • $\begingroup$ @RicPed I edited the answer to make the sets explicit. $\endgroup$ – Ian Mateus Mar 15 '14 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.