Take the 2-minute tour ×
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.

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.

Thanks in advance.

share|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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.