Results 1 to 13 of 13

Math Help - Prove the sum of all positive integers k...

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Prove the sum of all positive integers k...

    Prove that the sum of all positive integers k where 1 <= k <= n and gcd(k,n) = 1 is (1/2)n*phi(n).


    I don't even know where to begin with this. We've been going over primitive roots in class lately so it probably has something to do with them, but I have no idea where they come into the problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    For any n, \zeta=e^{2\pi i/n} is a primitive nth root of unity, and the other primitive roots are exactly the numbers \zeta^k, where gcd(k,n)=1. If you picture these on the unit circle and realize that the conjugate of a primitive root is also a primitive root, you can prove it that way.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    79
    Quote Originally Posted by LoblawsLawBlog View Post
    For any n, \zeta=e^{2\pi i/n} is a primitive nth root of unity, and the other primitive roots are exactly the numbers \zeta^k, where gcd(k,n)=1. If you picture these on the unit circle and realize that the conjugate of a primitive root is also a primitive root, you can prove it that way.
    Uh, we didn't learn anything like that in class.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    Ok, I tried to explain it using primitive roots because you said you're learning about them. The same proof will carry over to the group \mathbb{Z}/n\mathbb{Z}, since this group is isomorphic to the nth roots of unity. But you might not be doing much with groups if this is a number theory course, even though there's a lot of overlap.

    I guess the key facts are that \varphi(n) is the number of positive integers less than n that are relatively prime to n and also that gcd(n,k)=gcd(n,n-k). Does that help?

    You could probably also prove this using some facts about \varphi listed on its wikipedia page.

    edit: Ah, that explains it- there are two uses of the term primitive root. I thought you meant primitive roots of unity and I had never heard of the other meaning. Still, my second paragraph could still be used.
    Last edited by LoblawsLawBlog; February 28th 2011 at 11:56 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by uberbandgeek6 View Post
    Prove that the sum of all positive integers k where 1 <= k <= n and gcd(k,n) = 1 is (1/2)n*phi(n).


    I don't even know where to begin with this. We've been going over primitive roots in class lately so it probably has something to do with them, but I have no idea where they come into the problem.
    In any case is \displaystyle \sum_{k=1}^{n-1} k= \frac{n\ (n-1)}{2}. If n is prime then \varphi(n)= n-1 so that \displaystyle \sum_{k=1}^{n-1} k= \frac{n}{2}\ \varphi(n)...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2008
    Posts
    79
    @chisigma: I understand what you mean, but I'm not given that n is prime, so I don't see how that would work.

    @Loblawslawblog: I don't understand where you are going with the gcd(n, n-k). I get that it is true, but I don't see how that helps.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by uberbandgeek6 View Post
    @chisigma: I understand what you mean, but I'm not given that n is prime, so I don't see how that would work.
    One of Your hypothesis is that \forall k for which  0\le k\le n is \text {gcd} (k,n)=1 and that means that n is prime...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2008
    Posts
    79
    Quote Originally Posted by chisigma View Post
    One of Your hypothesis is that \forall k for which  0\le k\le n is \text {gcd} (k,n)=1 and that means that n is prime...

    Kind regards

    \chi \sigma
    Maybe I'm interpreting it wrong, but I think the problem means that it wants the sum of all k's that are relatively prime with n. So if n was not prime (say n = 10), it would be 1+3+7+9 = 20. Then (1/2)(10)phi(10) = 20 as well.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    Quote Originally Posted by uberbandgeek6 View Post
    @Loblawslawblog: I don't understand where you are going with the gcd(n, n-k). I get that it is true, but I don't see how that helps.
    Look at your example with n=10. 1 is relatively prime to 10, and so is 10-1=9. Likewise, 3 and 10-3=7 are both relatively prime to 10. Then the sum we're looking for is (1+9)+(3+7)=(4/2)(10).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by LoblawsLawBlog View Post
    Look at your example with n=10. 1 is relatively prime to 10, and so is 10-1=9. Likewise, 3 and 10-3=7 are both relatively prime to 10. Then the sum we're looking for is (1+9)+(3+7)=(4/2)(10).

    The hint, or info, given by LLLB is critical: let

    \Phi(n,k):=\{k\in\mathbb{N}\;;\;1\leq k\leq n\,,\,\,gcd(n,k)=1\}

    1) Prove that  k\in\Phi(n,k)\Longleftrightarrow n-k\in\Phi(n,k)

    2) Thus, we can pair up all the numbers in \Phi(n,k) in pairs (k,n-k) , with

    k\mbox{ and also }n-k\mbox{ in } \Phi(n,k)

    3) Since |\Phi(n,k)|=\phi(n) , there are \frac{1}{2}\phi(n) pairs as above, and

    since the sum of each such pair is n we're then done...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by LoblawsLawBlog View Post
    For any n, \zeta=e^{2\pi i/n} is a primitive nth root of unity, and the other primitive roots are exactly the numbers \zeta^k, where gcd(k,n)=1. If you picture these on the unit circle and realize that the conjugate of a primitive root is also a primitive root, you can prove it that way.
    How can you prove it that way?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    It's the same proof. A primitive root z^k would correspond to k in Z_n and the pairing (k,n-k) is just the pair z^k and its conjugate. Then the factor of 1/2 comes in because you only need to consider the top half of the unit circle. Add the exponents of the primitive roots and you're done.

    So basically there's no reason to go to complex numbers, but I tried to awkwardly jam them in because I thought the OP was learning something similar.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    That's what I thought. There's no reason to talk about primitive roots here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: January 31st 2010, 10:48 AM
  2. if x and n are positive integers....
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 6th 2009, 11:07 PM
  3. Prove 1 is the least element in the positive integers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 5th 2008, 02:04 AM
  4. Positive Integers
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 31st 2007, 01:48 PM
  5. Two Positive Integers....
    Posted in the Algebra Forum
    Replies: 6
    Last Post: May 20th 2007, 06:50 PM

Search Tags


/mathhelpforum @mathhelpforum