1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I assume you mean $2^{2015}$, correct? $\endgroup$ – xyzzyz May 27 '16 at 20:24
  • 5
    $\begingroup$ 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$. $\endgroup$ – Peter May 27 '16 at 20:24
  • 4
    $\begingroup$ Hint: $2^4\equiv -1\pmod{17}$. $\endgroup$ – André Nicolas May 27 '16 at 20:30
  • $\begingroup$ I dont know fermat's little theorem $\endgroup$ – Matt May 27 '16 at 20:54
  • 2
    $\begingroup$ It's well worth learning, if you want to answer this type of question. $\endgroup$ – Robert Israel May 27 '16 at 21:23
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is meaning of mod 17? $\endgroup$ – Matt May 27 '16 at 20:54
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas May 27 '16 at 21:07
  • 1
    $\begingroup$ @Raghav: You are welcome. $\endgroup$ – André Nicolas May 27 '16 at 22:27
  • $\begingroup$ +1. Very nicely explained according to the level of the OP! $\endgroup$ – N.S.JOHN May 28 '16 at 15:51
1
$\begingroup$

Use Little Fermat:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.