Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Have you already seen Euler's argument for $\varphi$ being multiplicative? –  Ian Mateus Mar 15 at 18:07
1  
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 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 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 Mateus Mar 15 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 at 18:12
show 3 more comments

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 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 at 18:44
add comment

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 at 18:57
1  
@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 Mateus Mar 15 at 19:10
    
@RicPed I edited the answer to make the sets explicit. –  Ian Mateus Mar 15 at 20:41
    
Thanks, I'll read it now:) –  Riccardo Mar 15 at 21:02
add comment

Your Answer

 
discard

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

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