this is a question from number theory

Question

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

Answer 1

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

Answer 2

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.