How to find the remainder $x^y\bmod z$ quickly?

Question

I am searching for any rule to find the remainder $x^y\bmod z$ where $x,y,z$ are positive integer.

Is there any rule to quickly find this remainder (without computing $x^y$)?

Answer 1

You can use Euler's theorem: $x^{\phi(z)} \equiv 1 \pmod z$ (assuming $x, z$ are coprime).

This means you can reduce $x^y \mod z = (x \mod z)^{y \mod \phi(z)}$.

Besides this, there's not much that can be said without knowing more about $x,y,z$.

Answer 2

Yes, there is.

As you ask about remainder, I guess we can assume that $x,y,z$ are positive integers. Then, what you are looking for is most probably the Euler-Fermat theorem, which states that $$x^{\varphi(z)}\equiv 1 \pmod{z}$$ if $x$ is coprime to $z$. Here $A\equiv B \pmod{z}$ means that $A$ and $B$ are congruent modulo $z$, i.e. they give the same remainder, that is, $z\,|\,A-B$. And, $\ \varphi(z)$ is the number of positive coprimes to $z$ which are less than $z$.

An important property of giving the same remainder is that it preserves addition and multiplication, in particular, if $x$ gives remainder $d$ modulo $z$, then $x\equiv d$ and we also have $x^y\equiv d^y\pmod{z}$.

Now, (supposing $x$ is coprime to $z$) you have to take the remainder of $y$ modulo $\varphi(z)$, say $y\equiv b\pmod{\varphi(z)}$, then we have $$x^y\equiv d^y\equiv d^b \pmod{z} \,.$$ In case, $\gcd(x,z)\ne 1$, we might have to find the factors of $z$ and find the remainders w.r.t. these factors, and then use the Chinese remainder theorem to glue the remainders together to get something modulo $z$.