1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about phi function

  1. Mar 19, 2013 #1
    1. The problem statement, all variables and given/known data
    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
    3. 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 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. jcsd
  3. Mar 19, 2013 #2
    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

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

    [tex]\frac{12\phi(12)}{2} = \frac{12 \times 4}{2} = 24[/tex]
    Write out similar equations for several other values of n and try to find a pattern.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted