Challenge Proof for the Best!

if a^k=b^kmod(n)
then a=bmod(n)
a^(k+1)=a*a^k
then a^(k+1)=bmod(n)b^kmod(n)=b^(k+1)mod(n)

Rap

If I'm reading this correctly, this one is not that hard. Are you sure you want the answer? It's not too late to turn away...


Given that a^(k+1) (mod m) = b^(k+1) (mod m) then a*a^k (mod m) = b*b^k (mod m).
a (mod m) * a^k (mod m) = b (mod m) * b^k (mod m)
But we are also given that a^k (mod m) = b^k (mod m) therefore, if a^k (mod m)>0, then a (mod m)=b (mod m)

The gcd(a,m)=1 requirement ensures that a (mod m) > 0. If you remove that requirement, then the proof is invalid since if a^k (mod m) = 0, then the relationship between a and b is not defined. You can see this using a=4, b=6, k=3 and m=8. 4^3 mod 8 = 0. 6^3 mod 8=0. 4^4 and 6^4 mod 8 are also zero, but 4 mod 8 does not equal 6 mod 8.

Oh God! This is so trivial. I guess this was given to us to prove how complicated our minds are. Just because of the fact that this was given as a challenge I was using all sorts of advanced techniques to do this. Thank you!

I'm a little confused. You're using mod too many times.

I have this so far:

a^(k+1) = b^(k+1) (mod m)

a * a^k = b * b^k (mod m)

Now what?

Does this imply that a = b (mod m) since a^k = b^k (mod m)?

Please advise. Thanks!

I jumped a little ahead on you. If A and B are congruent mod m, then you can show from the defininition of congruent that A mod m = B mod m. That is where all the mods come from. Your first line:

a^(k+1) = b^(k+1) (mod m)

should really be

a^(k+1) is congruent to b^(k+1) (mod m) therefore
a^(k+1) (mod m) = b^(k+1) (mod m)

Yup, finally I figured that out. Thanks!