Euler-Phi Function?

Question

I'm having a lot of problem with this proof. it states:

let n be an integer with n>1. prove that the sum of all positive integers k with 1 <= k < n and (k, n)=1 is .5n PHI(n).

i've been trying to use the following lemma as it was suggested in the "hint" section of the book:

let m be a positive integer with m>2. if a is a positive integer less than m with (a, m) =1, then (m-1, m)=1.

from that, you know that for some r, (n-rk, n) =1 where 0 <= n-rk < k.

does anyone have any suggestions for this problem? thanks a lot.

Answer 1

Use the fact that (k,n)=1 if and only if (n-k,n)=1.

So let P be the original sum.

(1) P = Sum (1<=k
We can rewrite this as:

(2) P = Sum (1<=k
But (n-k,n)=1 iff (k,n)=1, so you can write this as:

(3) P = Sum (1<=k
Adding (1) to (3), you get:

(4) 2P = Sum (1<=k
Factoring out n and dividing by 2, you get:

(5) P = 1/2 * n * Sum(1<=k
But the sum in that equation is just the definition of phi(n).