Euler function-Fermat's small theorem

Question

I can't figure out the way to solve this question,,,,

Let $n$ be a positive integer. Proof that the sum of integers in $\{1,2,\cdots,n\}$ coprime to $n$ is $\dfrac{n\phi(n)}2$.

For example, when $n = 12$, $$1 + 5 + 7 + 11 = 24 = \dfrac12 \times 12 \times 4 = \dfrac12 × 12 × \phi(12)$$ surely holds.

Answer 1

The following explicit derivation may be of some use.

Take $a,b$ to be coprime, i.e. $\gcd\left(a,b\right)=1$.

We then have:

$$ \gcd\left(a,b\right)=1=\gcd\left(a-b,b\right)=\gcd\left(b,a-b\right)=\gcd\left(a-\left(a-b\right),a-b\right)=\gcd\left(a,a-b\right) $$

where the property $\gcd\left(x,y\right)=\gcd\left(x-y,y\right)$ from Euclid's algorithm has been repeatedly applied. (Additional details: https://en.wikipedia.org/wiki/Euclidean_algorithm)

Therefore, $b$ and $a-b$ are both coprime to $a$ and whose sum is $b+a-b=a$.

An example:

$$ \gcd\left(9,2\right)=1=\gcd\left(9-2,2\right)=\gcd\left(7,2\right)=\gcd\left(2,7\right)=\gcd\left(9-7,7\right)=\gcd\left(9,7\right) $$.

I hope this helps.

Answer 2

Hint:

Can you show that there are $\phi(n)$ integers in $\{1,2,...,n\}$ coprime to $n$, and, if $a\in\{1,2,...,n\}$ is coprime to $n$, then so is $n-a$, and $n-a\ne a$, so the $\phi(n)$ integers can be put in pairs whose sum is $n$?