See here
Hi,
I need help with the following question in Euler's theorem:
Let me be a positive integer with m≠2. If {r1,r2,…..,rΦ(m)} is a reduced residue system modulo m, prove that
r1 + r2 + …….. r3 Ξ 0 mod n
If it helps, the back of the book tells me to use this lemma:
Let m > 2. If a is a positive integer less than m with (a,m) = 1, then (m-a, m) =1
Any help is appreciated
For every number there is so that . This is just the division algorithm as you have seem i.e. the remainder of upon division by . Every number relatively prime with is congruent to so that . Therefore, every number in the reduced residue system has to be congruent with all the numbers between and inclusively that are relatively prime with . Thus, the sum of all numbers in a reduced residue system is congruent to the sum of all numbers between and that are relatively primes to . This is exactly what PaulRS did.