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
    9
    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, 08:51 AM
  2. How to use Euler's theorem ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2010, 09:04 AM
  3. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 05:47 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 04:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum