# Thread: Sum of co-primes prior N

1. ## 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
$\displaystyle N=8$
Then
$\displaystyle 1+3+5+7=16$
and
$\displaystyle 16 \quad mod \quad 8=0$

Thank you all for your time and response

2. Originally Posted by gdmath
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
$\displaystyle N=8$
Then
$\displaystyle 1+3+5+7=16$
and
$\displaystyle 16 \quad mod \quad 8=0$

Thank you all for your time and response

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

$\displaystyle 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 $\displaystyle r\ne 1$

Tonio

3. Hi tonio,

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

4. Originally Posted by gdmath
Hi tonio,

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

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

6. One way is just to calculate the sum using a clever trick! Note that when $\displaystyle (j,n)=1$ we also have $\displaystyle (n-j,n)=1$, which allows us to compute the sum in two different ways :

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

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

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

and the result follows because $\displaystyle \phi(n)$ is even.

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

8. You're welcome! The solution is not mine, but I'll take credit for remembering it.