I just cam across a question in number theory which relates to Euler's totient function. The question is the following:

We have a positive integer $n>1$. Find the sum of all numbers $x$, such that $x\in {1, 2, ..., n}$, which are relatively prime with n.

I solved it in the following fashion: We have number $d$ which is relatively prime with $n$, we also have that $n-d$ is relatively prime with $n$. So the total addition, is $\frac{n*\phi(n)}{2}$

However, I know that there exists a solution with the use of the inclusion exclusion principle. Could you please explain to me how I could solve it using PIE?

  • 2
    $\begingroup$ The only way using inclusion/exclusion that jumps out is essentially a repeat of the PIE proof of the formula for Euler's totient function. $$\sum_{d \mid n} \mu(d)\cdot d \cdot \frac{\frac{n}{d}\bigl(\frac{n}{d} + 1\bigr)}{2} = \frac{n}{2} \sum_{d \mid n} \mu(d)\biggl(\frac{n}{d} + 1\biggr)$$ Not very instructive, and less elegant than your observation. $\endgroup$ – Daniel Fischer Aug 25 at 18:42

In general i like more your solution, but here we go. Recall that $[n]=\{1,2,\cdots, n\}.$ Consider $n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}$ call $A_r=\{x\in [n]:p_r|x\}$ and call $s(A)=\sum _{a\in A}a$ then by the PIE using a weight(mainly $s:[n]\longrightarrow \mathbb{R}$ defined before) $$s([n])-\sum _{i = 1}^k(-1)^{i-1}\sum _{X\in \binom{[k]}{i}}s\left (\bigcap _{x\in X}A_x\right ).$$ Now, notice that $s(A_j)=\sum _{p_j|d,d\leq n}d=p_j\sum _{i=1}^{n/p_j}i=p_j\binom{n/p_j+1}{2}=\frac{n}{2}(n/p_j+1).$ In general, you can check that $$s\left (\bigcap _{x\in X} A_x\right )=\prod _{x\in X} p_x \cdot \binom{n/(\prod _{x\in X} p_x)+1}{2}=\frac{n}{2}(n/(\prod _{x\in X} p_x)+1).$$ Plugging this in the equation and noticing that $s([n])$ can be placed inside the sum, you get $$\sum _{i = 0}^k(-1)^{i}\sum _{X\in \binom{[k]}{i}}s\left (\bigcap _{x\in X}A_x\right )=\frac{n}{2}\left (n+1+\sum _{i = 1}^k(-1)^{i}\sum _{X\in \binom{[k]}{i}}\left (n/(\prod _{x\in X} p_x)+1\right )\right )=\frac{n}{2}(n+1+n\prod _{x=1}^k (1-\frac{1}{p_x})+\sum _{i=1}^k(-1)^i\binom{k}{i})=\frac{n\cdot \varphi (n)}{2},$$ where in the last step we use the definition of $\varphi$ and the binomial theorem.

Edit: For clarification, first recall that inclusion exclusion principle means put everything, then take out repetitions, then add what you took out in the repetition, etc.. So, the $A_x$ are going to be the numbers you want to exclude, because if $a\in A_x$ then $a$ and $n$ are not coprime. Now, in the general theory of the PIE, you can use weights(you can think of it like in the probability sense, probability is a very special kind of weight of a set). In this case, our weight is the sum of the elements of the set. If you want to read more about this, i refer to you to theorem 8.1 here or Chapter of PIE in the book: "A course in enumeration" by M. Aigner.

Now, we have to compute, so first recall that $1+2+\cdots +n=\frac{n(n+1)}{2}=\binom{n+1}{2}$ so you kind of see that $\frac{n}{2}$ will play a good role in the understanding. Then we compute $s(A_j)$ for single sets $A_j$ noticing that every element is divisible by $p_j$ so we can think of a number there as $p_j\cdot i$ for $i$ less or equal to $n/p_j.$ When you understand this, you can try to compute it for general set. So the $\bigcap _x{\in X}A_x$ just means the set of elements divisible by every prime indexed by the set $X$ so every element will be a product of those primes times a number less than $\frac{n}{\text{multiplication of those primes}}.$ When you put everything together you notice that by factoring $\frac{n}{2}$ you get the usual PIE for computing $\varphi$ see for example the answers here.

| cite | improve this answer | |
  • $\begingroup$ Hello @Phicar, I'm having troubles understanding your solution, could you please explain it with fewer symbolisms, as I get lost in the many symbols which you use in your solution. It looks briliant, but unfortunately due to lack of experience I am unable to fully understand it. Could you please explain it with the use of fewer symbols? (by symols I refer to the $\bigcap$ etc. Thanks in advance :) $\endgroup$ – user814992 Aug 25 at 19:20
  • $\begingroup$ Hi @MichaelChristofer , i have edited. Let me know if this clarifies. Glad to help. $\endgroup$ – Phicar Aug 25 at 19:33
  • $\begingroup$ Thanks a lot @Phicar, you're brilliant, have a good day $\endgroup$ – user814992 Aug 25 at 19:47
  • $\begingroup$ Sir, please help me with the problem at math.stackexchange.com/questions/3797044/… $\endgroup$ – Junk Warrior Sep 3 at 0:31

Your Answer

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