Results 1 to 5 of 5

Math Help - congruence question

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    12

    congruence question

    Let m, n, r, e be pos. integers. I am trying to show that given m = n (mod e*r) that m^e=n^e (mod r*e^2). I have tried using the binomial theorem but keep running into problems.

    Could someone help please?? thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,185
    Thanks
    404
    Awards
    1
    Quote Originally Posted by arlingtonbassett View Post
    Let m, n, r, e be pos. integers. I am trying to show that given m = n (mod e*r) that m^e=n^e (mod r*e^2). I have tried using the binomial theorem but keep running into problems.

    Could someone help please?? thanks!
    This is a little rough, but perhaps you can clean it up and make everything neat.

    The first condition says
    m \equiv n \text{ (mod (er))}

    So we know that
    m = a(er) + b
    n = c(er) + d
    where a, b, c, d are integers and 0 <= b < er and 0 <= d < er. Since m = n (mod er) we know that b = d.

    Now, let's form m^e.
    m^e = (a(er) + b)^e = a^e (er)^e + e a^{e - 1}(er)^{e - 1}b + \text{ ... } + e a(er)b^{e-1} + b^e

    Note that every term but the last is proportional to e^2r. Thus m^e has the form:
    m^e = p(e^2r) + b^e

    where p is an integer. We don't need the usual 0 <= b^e < e^2 r condition as you will see.

    Now do the same for n^e. Then use the fact that b = d from the initial condition.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    12
    thanks for that. it all makes sense except two of the beginning lines...how did you get

    m=aer+b and n= cer+d?

    everything else makes sense to me.

    thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,185
    Thanks
    404
    Awards
    1
    Quote Originally Posted by arlingtonbassett View Post
    thanks for that. it all makes sense except two of the beginning lines...how did you get

    m=aer+b and n= cer+d?

    everything else makes sense to me.

    thanks!
    Sorry, I wasn't very clear about that was I? We can get both equations by the division algorithm.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2011
    Posts
    12
    nm got it thanks again for the help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2010, 08:20 AM
  2. Possible Congruence Question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 3rd 2009, 04:32 PM
  3. Congruence question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 13th 2009, 10:51 AM
  4. Congruence question
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: January 6th 2009, 09:46 AM
  5. Congruence question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 11th 2007, 04:31 PM

Search Tags


/mathhelpforum @mathhelpforum