# question relating to the Euler's totient function

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?

• 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. – 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.
• 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 :) – user814992 Aug 25 at 19:20