Is it true that $a^k\equiv a^\ell \mod n$?

Question

Let $a, b\in\mathbb{Z}$, $n\in\mathbb{N}$, and $k, \ell\in \mathbb{N}$, such that $k\equiv \ell \mod{n}$ and $a\equiv b\mod n$.

Is it true that $a^k\equiv a^\ell \mod n$? If so, prove it. If not, find a counterexample.

I suppose it's true, but I'm not sure how to prove it.

Answer 1

Hint: What if $n=3$, $k=1$, $\ell=4$ and $a=2$?

Answer 2

No. At least not generally. See: $$y\equiv b\bmod m\implies y=mx+b$$ This means only if y and m share a factor (or x but we generally ignore it) will b share a factor. So if y is a power based on a value that doesn't share a factor, all it's remainders b wont share a factor with the modulus m. Only when the number of of values less than m, that don't share a factor with m, ends up being a divisor of m, will your statement be true. This restricts it pretty much to powers of 2. A few more edge cases exist like 6, but that's basically it. if they share a factor it will change for example every value with a factor (2) in common with 8 will hit 0 mod 8 and stay there for any higher powers.It will only hit remainders that have that gcd in common.