Discrete Math: If a=b(mod m) then (a^n)=(b^n)(mod m)

[shooger]

Alright first of all this is my first post so hello world!

I've been up all night (literally, have not slept) trying to figure this out. The question is:

PROVE :
If a=b(mod m) then (a^n)=(b^n)(mod m)

I understand that a=b(mod m) implies that a=mk+b, which would presumably setup the fact that (a^n)=(mk+b)^n, but now what? You cannot simplify (mk+b)^n to get (b^n)(mod m). Or can you? Am I going about this the complete wrong way? Is this way easy and I just haven't slept enough?

A pointer in the right direction would be WONDERFUL! Thanks for your time

 

[shooger]

So to add to this...

I realized that this is obviously true because

a=mk+b means that m|b-a

If we let a=2 and b=5 and m=3, we have

m|b-a because 3|3

Similarly, m|(b^2)-(a^2) because 3|(25-4)

This holds true for every exponent I have checked... but I obviously cannot check them all. Is it proved then? Does anyone know of some rule that says something like this? :?

EDIT: (just realized you could edit :roll: )

I have another idea. If we say that, for the sake of this problem, n=2, we have:

a^2=(mk+b)(mk+b) which simplifies to
(a^2)-(b^2)=mk, meaning m|(a^2-b^2) and a^2=b^2(mod m)

Replacing n=2 with n=any integer,
Do we prove the original problem?

 

[pka]

You do know that \(\displaystyle a \equiv b\;\bmod (m)\; \Rightarrow \;m|(a - b)\)?
Moreover, you know that \(\displaystyle a^n - b^n = \left( {a - b} \right)\left( {\sum\limits_{k = 0}^{n - 1} {a^{n - 1 - k} b^k } } \right)\).
Now it should be clearly true.

 

[shooger]

Thank you for your reply.

Though what you're saying makes sense, I do not think that this is what he's looking for. We have not discussed Rieman sums in this class.. can anyone else offer an explanation without them? Thanks!

 

[pka]

I do not think that this is what he's looking for. We have not discussed Rieman sums in this class.. can anyone else offer an explanation without them?

GOOD GRIEF! What makes you think that anything I wrote has to do with Riemann Sums? What I did was to point that this is problem about factoring that is hardly beyond beginning algebra.

 

[daon]

You showed n=1,2.

Assume for the sake of induction its true up to a positive integer k.

a^(k+1)-b^(k+1) = a*a^k - b*b^k

Since a = b + m*r for some r, replace a with such:

a*a^k - b*b^k = (b+m*r)a^k - bb^k = b(a^k-b^k) + (m*r)*a^k

a^k - b^k = m*p for some p by the induction hypothesis, so substitute:

b(a^k-b^k) + m*r*a^k = b(m*p) + m*r*a^k = m(b*p + r*a^k)

Therefore, a^(k+1)-b^(k+1) = m(b*p + r*a^k), and hence a^(k+1) - b^(k+1) is divisible by m.

Pka's is a much cleaner proof though without all the messy algebra.

This holds true for every exponent I have checked... but I obviously cannot check them all. Is it proved then? Does anyone know of some rule that says something like this? :?

edit to add: No, never. No matter how many specific integers you check, it is not a proof.

 

[PAULK]

Alright first of all this is my first post so hello world!

I've been up all night (literally, have not slept) trying to figure this out. The question is:

PROVE :
If a=b(mod m) then (a^n)=(b^n)(mod m)

I understand that a=b(mod m) implies that a=mk+b, which would presumably setup the fact that (a^n)=(mk+b)^n, but now what? You cannot simplify (mk+b)^n to get (b^n)(mod m). Or can you? Am I going about this the complete wrong way? Is this way easy and I just haven't slept enough?

A pointer in the right direction would be WONDERFUL! Thanks for your time

a = b + mk

a^n = (b + mk)^n

Binomial expansion:

a^n = b^n + lots of terms with at least one factor of m.

a^n = b^n + m(some integer)

So ....