# How to find remainder of a very large number when divisor is 17?

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?

• I assume you mean $2^{2015}$, correct? May 27 '16 at 20:24
• You can use Fermat's little theorem and reduce the exponent modulo $16$. You get $2^{15}$. Moreover, since $2^{16}=1$ modulo $17$, the answer is just the inverse of $2$ modulo $17$, and this is $9$. May 27 '16 at 20:24
• Hint: $2^4\equiv -1\pmod{17}$. May 27 '16 at 20:30
• I dont know fermat's little theorem
– Matt
May 27 '16 at 20:54
• It's well worth learning, if you want to answer this type of question. May 27 '16 at 21:23

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

• What is meaning of mod 17?
– Matt
May 27 '16 at 20:54
• We write $a\equiv b\pmod{m}$ if $m$ divides $a-b$. But if you are not familiar with modular notation, maybe I should write a different version of the answer. It will take some time, say $15$ minutes. May 27 '16 at 21:07
• @Raghav: You are welcome. May 27 '16 at 22:27
• +1. Very nicely explained according to the level of the OP! May 28 '16 at 15:51

Use Little Fermat:

$$2^{16}\equiv 1\mod17,\enspace\text{hence}\enspace2^{2015}\equiv2^{2015\bmod16}=2^{15}=2^{-1}=9\mod 17.$$