# congruence question

• May 7th 2011, 06:53 PM
arlingtonbassett
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.

• May 7th 2011, 08:39 PM
topsquark
Quote:

Originally Posted by arlingtonbassett
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.

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
• May 8th 2011, 09:15 AM
arlingtonbassett
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!
• May 8th 2011, 10:59 AM
topsquark
Quote:

Originally Posted by arlingtonbassett
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
• May 8th 2011, 11:09 AM
arlingtonbassett
nm got it thanks again for the help