For $n > 2, n \in \mathbb{Z}$, show the sum of integers coprime to $n$ in the range $[1,n-1]$ is equal to $\frac{1}{2}n \phi(n)$
Firstly $\phi(n)$ is Euler's totient function, the number of integers that are coprime to $n$ for $1 \leq x < n$.
The way I was going about answering this question was considering $n-x$, where $n – x$ (mod $n$) $\equiv – x$ (mod $n$), and as gcd($-x,n$) = 1 they share similar properties, but are not the same ie. $x \neq n-x$ (which I struggled to prove rigorously).
I'm really struggling to think of any other options or how it ends up being the expected value to the sum.
Thanks,
Best Answer
Suppose $A=\{a_1,a_2......a_{\phi(n)}\}$ be set of integers less than and coprime to $n$. Now consider the set $\{n-a_1,n-a_2......n-a_{\phi(n)}\}$ then this set also consist of elements which are less than and coprime to $n$.
So $A=\{n-a_1,n-a_2......n-a_{\phi(n)}\}$.
and therefore sum
$S=a_1+a_2......+a_{\phi(n)}. . . . (1)$
$S=n-a_1+n-a_2+......+n-a_{\phi(n)}. . . . (2)$
adding equation (1) and (2) we have
$2S=n\phi(n)$
So $S=\frac{1}{2}n\phi(n)$