does $a^b \pmod p = (a \pmod p)^b$

Question

I'm not sure whether this is true or not - does $a^b \pmod p = (a \pmod p)^b$?

Searched online but couldn't find a clear answer. Thanks!

Answer 1

Probably the main reason you can't find a clear answer is because the notation is a bit confusing. When you work with the integers "modulo $p$", you aren't working with integers any more, but rather equivalence classes of integers. Writing $5\pmod3=2$ is an abuse of notation, as what you're really saying is $$ 5 \equiv 2 \pmod 3 $$ that is, "$5$ and $2$ are in the same equivalence class modulo $3$." In other words, $5-2$ is a multiple of $3$ (this is all that "$\pmod3$" really says). It's generally dangerous to think of "$\pmod3$" as a function into the integers because things like $(a\pmod p)^b$ aren't so clear. For example, should I think of $(5\pmod3)^5$ as $2^5=32$? If I do then the answer to your question is "no" but this is likely not what you had in mind.

From the perspective of equivalence classes, the question becomes more straightforward: is the mapping $a\mapsto a^b$ well defined modulo $p$? That is, if $a\equiv a'\pmod p$, then is $a^b\equiv(a')^b\pmod p$ also? This is likely the question you meant to ask, and the answer to this question is yes! This means that computing $a^b\pmod p$ can be done by first computing $a^b$ and then looking at its equivalence class modulo $p$, and also by taking $a$'s equivalence class modulo $p$ and then working with multiplication in this world.

The reason why this is true is because multiplication is well-defined modulo $p$: if $a\equiv a'\pmod p$ and $b\equiv b'\pmod p$, then $ab\equiv a'b'\pmod p$. To see this, we can just use the definition: we need to show that $ab-a'b'$ is a multiple of $p$, which follows because $$ ab-a'b' = ab - ab' + ab' - a'b' = a(b-b') + (a-a')b' $$ Since $a-a'$ and $b-b'$ are multiples of $p$ by assumption, the right hand side is a multiple of $p$ and therefore $ab\equiv a'b'\pmod p$, as desired.

A word of warning however, negative exponents can make sense modulo $p$ too, despite this not making sense over the integers. The inverse $a^{-1}$ is supposed to be a number that, when multiplied by $a$, gives you $1$. In the context of the integers, $5^{-1}=\frac15$ satisfies this, but is definitely not an integer. However, if we look at equivalence classes modulo $3$, we can actually find some $a$ such that $5a\equiv1\pmod3$. Indeed, here we can take $a=2$, then $5a\equiv10\equiv1\pmod3$, and we usually write this as $$ 5^{-1}\equiv2\pmod3 $$ and this is certainly not something you could have computed by taking $5^{-1}$ first in the world of integers (er, rationals) and then finding an equivalence class modulo $3$.