1. Mar 19, 2013

### port31

1. The problem statement, all variables and given/known data
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
3. 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 im 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.

2. Mar 19, 2013

### 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.