What is the Proof for the Summation of Integers using Euler's Phi Function?

[port31]

Homework Statement

Prove:
$\sum_{k<n} k= \frac{n \phi (n)}{2}$
gcd(k,n)=1
$\phi$ is Euler's phi function or Euler's totient function

The Attempt at a Solution

So the sum should be
$1+2+3+...+(n-2)+(n-1)$
which will equal $\frac{n^2-n}{2}$
using the formula for the sum of integers by gauss.
I can get this equal to the right side if n is prime
then $\phi (n) = n-1$ but for example if n=12 and k=11 this doesn't seem to work.
It seem that n need to be prime for this to work, unless I am missing something.
Well I guess if k is less than n, that means its any integer less than n and if their
gcd(n,k)=1 then n must be prime.

 

[Petek]

The summation is taken over all k < n such that k and n are relatively prime (in other words, such that gcd(k,n) = 1). For example, if n = 12, the sum is

$$1 + 5 + 7 + 11 = 24$$
(because 1, 5, 7 and 11 are all the integers less than 12 that are relatively prime to 12). Also

$$\frac{12\phi(12)}{2} = \frac{12 \times 4}{2} = 24$$
Write out similar equations for several other values of n and try to find a pattern.