Results 1 to 8 of 8

Math Help - Sum of co-primes prior N

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    Sum of co-primes prior N

    Is the following valid?

    Proove that all integers prior to N that are co-primes to N (including 1) their sum is divisible by N

    Example
    Let
    <br />
N=8<br />
    Then
    <br />
1+3+5+7=16<br />
    and
    <br />
16 \quad mod \quad 8=0<br />

    Thank you all for your time and response
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by gdmath View Post
    Is the following valid?

    Proove that all integers prior to N that are co-primes to N (including 1) their sum is divisible by N

    Example
    Let
    <br />
N=8<br />
    Then
    <br />
1+3+5+7=16<br />
    and
    <br />
16 \quad mod \quad 8=0<br />

    Thank you all for your time and response

    If you know that all the residues modulon N that are coprime with N are a multiplicative group, which is usually denoted by \left(\mathbb{Z}\slash N\mathbb{Z}\right)^{*}=:\mathbb{Z}^*_N, then the result is pretty easy to show: take an element  r coprime with N DIFFERENT from 1, and put:

    S:=\sum\limits_{(i,N)=1}i\Longrightarrow\,rS=\sum\  limits_{(i,N)=1}ri=\sum\limits_{(i,N)=1}i=S\Longri  ghtarrow (r-1)S=0\Longrightarrow S=0\ , since  r\ne 1

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    77
    Hi tonio,
    First of all hank you for your reply.

    Indeed i am not familiar with multiplicative groups. I am trying to find resources on this.
    However you write that:

    If you know that all the residues modulon that are coprime with are a multiplicative group
    do we know this, or need to prove that "all the residues modulo are coprime with " for special cases of N?

    Thank you again
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by gdmath View Post
    Hi tonio,
    First of all hank you for your reply.

    Indeed i am not familiar with multiplicative groups. I am trying to find resources on this.
    However you write that:



    do we know this, or need to prove that "all the residues modulo are coprime with " for special cases of N?

    Thank you again

    We need it and we do have it as I wrote it since it is not true in general that ALL the residues modulo N are coprime to N...in your example, with N = 8, the residues 0,2,4,6 are not coprime with 8.
    All the NON-ZERO residues modulo N are coprime to N iff N is a prime.

    And perhaps you shouldn't look for resources in the web about group theory: it's too wide and complex a subject to read about it just to solve this problem.

    There must be some more elementary way to solve then this problem, but right now I can't see it.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    77
    Ok. I try to see how to manage this issue, for a while - if i cant make it i leave it.

    Thank you again my friend.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    One way is just to calculate the sum using a clever trick! Note that when (j,n)=1 we also have (n-j,n)=1, which allows us to compute the sum in two different ways :

    \sum_{j=1,\  (n,j)=1}^nj = \sum_{j=1,\  (n,j)=1}^n(n-j)

    so 2\sum_{j=1,\  (n,j)=1}^nj = \sum_{j=1,\  (n,j)=1}^nn = n\phi(n)

    therefore \sum_{j=1,\  (n,j)=1}^nj = \frac{n\phi(n)}{2}

    and the result follows because \phi(n) is even.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2009
    Posts
    77

    marvellous

    One way is just to calculate the sum using a clever trick! Note that when we also have
    Marvellous!

    Not only we have the divisbility but also "a taste" of the sum.

    Thank you
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    You're welcome! The solution is not mine, but I'll take credit for remembering it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial with prior?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 15th 2010, 09:37 PM
  2. Jeffreys Prior
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 23rd 2010, 04:02 PM
  3. Bayesian prior
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 22nd 2010, 03:42 AM
  4. Prior/Posterior Distribution
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 5th 2009, 10:59 PM
  5. Normalization prior to ANOVA
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: August 25th 2008, 12:52 PM

Search Tags


/mathhelpforum @mathhelpforum