- #1
port31
- 20
- 0
Homework Statement
Prove:
[itex] \sum_{k<n} k= \frac{n \phi (n)}{2} [/itex]
gcd(k,n)=1
[itex] \phi [/itex] is Euler's phi function or Euler's totient function
The Attempt at a Solution
So the sum should be
[itex] 1+2+3+...+(n-2)+(n-1) [/itex]
which will equal [itex] \frac{n^2-n}{2} [/itex]
using the formula for the sum of integers by gauss.
I can get this equal to the right side if n is prime
then [itex] \phi (n) = n-1 [/itex] 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.