[Math] How to find remainder of a very large number when divisor is 17

Question

How to find the remainder when $2^{2015}$ is divided by $17$?
I tried dividing $2,4,8,16$ etc by $17$ and finding the remainder in each case to form some particular sequence but failed can someone help and please explain in a very simple language?

Answer 1

The prime $17$ is fairly special, it is nearly a power of $2$. Specifically, $2^4\equiv -1\pmod{17}$. Now $2012=(4)(503)$, so $2^{2012}\equiv -1\pmod{17}$, and therefore $2^{2015}\equiv -8\equiv 9\pmod{17}$.

Added: It is now clear that OP is not familiar with "arithmetic modulo $m$." There are two alternatives. The right one is to devlop the basics, since they will continue to be useful. Or else one can find an alternate procedure. We will do that. It will be somewhat ugly.

Note that $2^4=(-1+17)$. So $2^{2012}=(2^4)^{503}=(-1+17)^{503}$. Imagine expanding using the binomial theorem. We get $$(-1+17)^{503}=(-1)^{503}+\binom{503}{1}(-1)^{502}(17)+\cdots.$$ The important thing to notice is that all the terms after $(-1)^{503}$ are divisible by $17$.

So $(-1+17)^{503}$ is $1$ less than a multiple of $17$. Thus $2^{2012}=17k+16$ for some integer $k$.

It follows that $2^{2015}=8(17k+16)=17(8k+7)+9$. So $2^{2015}$ is $9$ more than a multiple of $17$. Thus the remainder when we divide $2^{2015}$ by $17$ is $9$.

Another way: Alternately, we can compute the remainders when $2^0$, $2^1$, $2^2$, and so on are divided by $17$. We are looking for a pattern.

The remainders are $1, 2,4,8,16,15,13, 9, 1, 2, 4, \dots$. One needs to show that the pattern persists. After one has done that, it becomes clear that the remainder of $2^{2016}$ is $1$, so the remainder of $2^{2015}$ is the entry "before" $1$, which is $9$.