Results 1 to 4 of 4

Math Help - Euler's Theorem

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    See here
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    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).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by htata123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. How to use Euler's theorem ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2010, 10:04 AM
  3. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 06:47 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 05:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum