# Math Help - Euler's Theorem

1. ## Euler's Theorem

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

2. See here

3. Hey thanks for your help on the question. I'm still having a little trouble following the first step which is where you say the summation of x is obviously congruent to k(mod m).

4. Originally Posted by htata123
Hey thanks for your help on the question. I'm still having a little trouble following the first step which is where you say the summation of x is obviously congruent to k(mod m).
For every number $x$ there is $0\leq x_0 < m$ so that $x\equiv x_0(\bmod m)$. This is just the division algorithm as you have seem i.e. the remainder of $x$ upon division by $m$. Every number $r$ relatively prime with $m$ is congruent to $0\leq r_0 < m$ so that $(r_0,m)=1$. Therefore, every number in the reduced residue system has to be congruent with all the numbers between $1$ and $m$ inclusively that are relatively prime with $m$. Thus, the sum of all numbers in a reduced residue system is congruent to the sum of all numbers between $1$ and $m$ that are relatively primes to $m$. This is exactly what PaulRS did.