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 want to know what happens when $M$ to the power $N$ is divided by $K$, where $M$, $N$, and $K$ are natural numbers.

share|improve this question
1  
I have changed your question to try to make more sense of it - please check to see if that's what you wanted. Also - what do you want to know? –  mixedmath Jul 11 '11 at 17:17
2  
I think more of the original wording should be kept, as in "when $m^n$ is divided by $k$". –  André Nicolas Jul 11 '11 at 17:20
3  
@mixedmath: at the moment the OP's question is so manifestly incomplete that perhaps it's best to assume for now that he submitted it too soon and give him a chance to edit it himself. @Gaurav: you haven't asked a question yet, not even close. What you have written has the same form as "What happens when $67$?" It doesn't stand on its own as a question! –  Pete L. Clark Jul 11 '11 at 17:22
1  
Nothing happens. :-) –  lhf Jul 11 '11 at 17:27
4  
Why did someone upvote this? –  Eric Naslund Jul 13 '11 at 19:00
show 4 more comments

2 Answers

I think if k < $m^n$ some quotient and remainder(if not divided completely) gets generated

else if k > $m^n$ then $m^n$ is the remainder with 0 (zero) as quotient...

share|improve this answer
add comment

I will interpret your question as meaning that you would like information of a general character about the remainder when $m^n$ is divided by $k$.

For specific integers $m$, $n$, and $k$ we can simply calculate. However, ordinary methods of calculation quickly run into trouble when the exponent $n$ is large. For example, suppose that we want the remainder when $7^{99}$ is divided by $17$. It would be painful to calculate $7^{99}$, and then divide by $17$!

The following result is very helpful, when $k$ is prime.

Theorem: (Fermat's "little" Theorem) Let $k$ be prime, and suppose that $m$ is not divisible by $k$. Then the remainder when $m^{k-1}$ is divided by $k$ is equal to $1$.

Take for example $m=7$, $k=17$. Then Fermat's Theorem tells us that when we divide $7^{16}$ by $17$, we get a remainder of $1$.

It is fairly easy to see that therefore the remainder when $7^{32}$ is divided by $17$ is also $1$, as is the remainder when $7^{48}$ is divided by $17$, as is the remainder when $7^{64}$ is divided by $17$, and so on.

So the remainder when $7^{96}$ is divided by $17$ is $1$. It follows that the remainder when $7^{97}$ is divided by $17$ is $7$. To find the remainder when $7^{98}$ is divided by $17$, multiply $7$ by $7$, find the remainder. We get $15$. Finally, to find the remainder when $7^{99}$ is divided by $17$, multiply $15$ by $7$, find the remainder. We get $3$.

Let's use the same idea to find, quite quickly, the remainder when $5^{2012}$ is divided by $17$. Note that $2012=2000+12=(125)(16)+12$. The remainder when $5^{16}$ is divided $17$ is $1$, by Fermat's Theorem, and therefore the remainder when $5^{2000}$ is divided by $17$ is also $1$. So all we need to do is to find the remainder when $5^{12}$ is divided by $17$.

This is a pretty small problem, but I would like to introduce a "trick" which is actually a method of great practical importance. It is called by various names, such as the Binary Method of Exponentiation.

The remainder when $5^2$ is divided by $17$ is $8$. So the remainder when $5^4$ is divided by $17$ is the same as the remainder when $8\times 8$ is divided by $17$. This is $13$. The remainder when $5^8$ is divided by $17$ is therefore $16$. Finally, since $8+4=12$, the remainder when $5^{12}$ is divided by $17$ is $4$. (Do check my calculations: the idea is right but I am accident-prone).

Back to your problem, with general $m$, $n$, and $k$. I should mention that there is a generalization of Fermat's Theorem to non-prime $k$. This generalization is called Euler's Theorem, and involves the Euler $\varphi$-function. If you are curious, you can find plenty of information on both theorems in Wikipedia, or in any introductory Number Theory book.

share|improve this answer
add comment

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.