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 $\displaystyle x$ there is $\displaystyle 0\leq x_0 < m$ so that $\displaystyle x\equiv x_0(\bmod m)$. This is just the division algorithm as you have seem i.e. the remainder of $\displaystyle x$ upon division by $\displaystyle m$. Every number $\displaystyle r$ relatively prime with $\displaystyle m$ is congruent to $\displaystyle 0\leq r_0 < m$ so that $\displaystyle (r_0,m)=1$. Therefore, every number in the reduced residue system has to be congruent with all the numbers between $\displaystyle 1$ and $\displaystyle m$ inclusively that are relatively prime with $\displaystyle m$. Thus, the sum of all numbers in a reduced residue system is congruent to the sum of all numbers between $\displaystyle 1$ and $\displaystyle m$ that are relatively primes to $\displaystyle m$. This is exactly what PaulRS did.