Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$)?

share|cite|improve this question
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$.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.