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.