1
$\begingroup$

On this page, there is a proof that uses the inclusion-exclusion principle to provide a formula for the value of Euler's totient function. I would be grateful if someone could explain the reasoning behind the final step, namely: $$ \begin{aligned} n \left(1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_i p_j} -\sum \frac{1}{p_i p_j p_k} + \cdots + (-1)^{|P|} \frac{1}{p_1 p_2 \cdots p } \right) \ &= n \prod_{p \in P} \left(1-\frac{1}{p}\right) \end{aligned} $$ The author states that the final step relies on the following identity: $$ \begin{aligned} \prod_{i=1}^n (1 - x_i) &= 1 - \sum x_i + \sum x_i x_j - \sum x_i x_j x_k + \cdots + (-1)^n x_1 x_2 \cdots x_n \\ & = \sum_{I \subset {1, 2, \ldots, n}} (-1)^{|I|}\prod_{i \in I} x_i \end{aligned} $$

I am aware of other proofs of Euler's phi function which rely on first proving that it is a multiplicative function. I'm not interested in that aspect. The author of the first link explicitly states his preference for a method that does not require it. I'm interested in how one proceeds from the inclusion-exclusion expression to the product. Is it simply from the binomial expansion of the product?

Thanks

CL

$\endgroup$
1
$\begingroup$

Consider the product $(1-x_1)(1-x_2) \cdots (1-x_n)$. When you expand it out, you get $1 - x_1 - x_2 \cdots - x_n + x_1 x_2 + x_1 x_3 + \cdots + (-1)^n x_1 \cdots x_n$. Observe that each term in the resulting expansion is actually a product of $n$ terms, each of which is either equal to $1$ or $-x_i$ for some $i$. For example, the term $x_3 x_5$ in the expansion is really obtained due to the product $(1)(1)(-x_3)(1)(-x_5)(1) \cdots (1)$. This term can be expressed in the form $(-1)^{|I|} \Pi_{i \in I} x_i$, where $I = \{3,5\}$. Of course, $I$ can be any subset of $\{1,2,\ldots,n\}$, and so you obtain the general formula above.

$\endgroup$

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.