# this is a question from number theory

I want to know what happens when $M$ to the power $N$ is divided by $K$, where $M$, $N$, and $K$ are natural numbers.

-
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
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
@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
–  lhf Jul 11 '11 at 17:27
Why did someone upvote this? –  Eric Naslund Jul 13 '11 at 19:00
show 4 more comments

## 2 Answers

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.

-
add comment

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

-
add comment