# what is the rule to find the remainder for $\frac{x^y}{z}$

I am searching for any rule to find the remainder for $\frac{x^y}{z}$?

where x,y,z are positive integer.

if there is any rule to find the ans quickly then plz help me.

-
It only depends on the vales of $x,y$ and $z$. –  Inceptio Mar 26 '13 at 18:22
You are more likely o get a useful answer if you give one or two concrete examples. –  André Nicolas Mar 26 '13 at 18:37
Is $x$ coprime to $z$? –  Math Gems Mar 26 '13 at 18:55

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$.

-
Note the Euler's theorem requires $\:(x,z) = 1.\ \$ –  Math Gems Mar 26 '13 at 18:54
Whoops, missed that. Thanks, edited. –  Yoni Rozenshein Mar 26 '13 at 19:01

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$.

-