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?
 A: 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.
