# Prove the sum of all positive integers k...

• Feb 28th 2011, 09:09 AM
uberbandgeek6
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.
• Feb 28th 2011, 02:16 PM
LoblawsLawBlog
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.
• Feb 28th 2011, 06:21 PM
uberbandgeek6
Quote:

Originally Posted by LoblawsLawBlog
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.
• Feb 28th 2011, 06:55 PM
LoblawsLawBlog
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.
• Feb 28th 2011, 07:21 PM
chisigma
Quote:

Originally Posted by uberbandgeek6
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$
• Mar 1st 2011, 05:44 AM
uberbandgeek6
@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.
• Mar 1st 2011, 06:46 AM
chisigma
Quote:

Originally Posted by uberbandgeek6
@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$
• Mar 1st 2011, 06:57 AM
uberbandgeek6
Quote:

Originally Posted by chisigma
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.
• Mar 1st 2011, 07:35 AM
LoblawsLawBlog
Quote:

Originally Posted by uberbandgeek6
@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).
• Mar 1st 2011, 10:28 AM
tonio
Quote:

Originally Posted by LoblawsLawBlog
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...(Clapping)

Tonio
• Mar 1st 2011, 07:11 PM
Bruno J.
Quote:

Originally Posted by LoblawsLawBlog
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?
• Mar 2nd 2011, 08:10 AM
LoblawsLawBlog
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.
• Mar 2nd 2011, 08:23 AM
Bruno J.
That's what I thought. There's no reason to talk about primitive roots here. :)