# Find the remainder when $2^{2013}$ is divided by $17$.

This question was asked me in binomial theorem chapter. I don’t know if I am doing it right. Here are my steps

Let $(1+x)^n=C_0+C_1x+C_2x^2+\cdots C_n x^n$

Let $x=1,n=2013$

$2^{2013}=C_0+C_1+C_2+\cdots C_{2013}$

Let $2^{2013}=17k+r$ from here I am lost. Help.

You don't even need the binomial theorem, you may just exploit the fact that $2^4$ and $17$ differ by one:

$$2^{2013}= 2\cdot(2^4)^{503} \equiv 2\cdot(-1)^{503} \equiv -2 \equiv \color{red}{15}\pmod{17}.$$

• That’s nice approach. But modular arithmetic isn’t thought in my school. Also I need to solve by binomial since it is given in that chapter. Commented Jun 23, 2017 at 14:21
• You are asked for a remainder and don't have modular arithmetic? Commented Jun 23, 2017 at 14:34

Since you need to go "binomially" you might go like this.

Given that $$2^{\,4} = 16 = 17 - 1$$

then \eqalign{ & \left( {1 + 1} \right)^{\,2013} = \left( {1 + 1} \right)^{\,4 \cdot 503 + 1} = 2\left( {1 + 1} \right)^{\,4 \cdot 503} = 2\left( {17 - 1} \right)^{\,503} = \cr & = 2\sum\limits_{0\, \le \,k\, \le \,503} {\left( \matrix{ 503 \cr k \cr} \right)\left( { - 1} \right)^{\,503 - k} 17^{\,k} } = 2\left( { - 1 + \sum\limits_{1\, \le \,k\, \le \,503} {\left( \matrix{ 503 \cr k \cr} \right)\left( { - 1} \right)^{\,k + 1} 17^{\,k} } } \right) \cr}

The terms in the last summation are all multiple of $17$, so their remainder is null.

Thus $r=-2$, i.e. $r=15$.

When $n$ is odd, the polynomial $x^n+1$ is a multiple of $x+1$, and so:

When $n$ is odd, the polynomial $x^{4n}+1$ is a multiple of $x^4+1$.

Apply this to $x=2$ and $n=503$ to get that $a=2^{2012}+1$ is a multiple of $17$.

Write $a=17q$.

Then $2^{2013}=2(a-1)=2(17q-1)=17(2q)-2=17(2q-1)+15$ and so the remainder is $15$.

• That’s a nice logic! I am not sure my examiner will accept this procedure. (Since this question came from binomial theorem). Commented Jun 23, 2017 at 14:48

$$2 \cdot (17 -1) ^{503} = 2 \cdot \sum_{k=0}^{n=503} 17^k(-1)^{503-k} = 2 \cdot {503\choose0}\times (-1)^{503} (mod~17)$$

You needed an $x$ of $17$, and use $y = -1$ to easily fit $2^n$.

In the expanded summation everything except the first term $k=0$ equals $0~mod~17$. For $k=0$ you ended up with $-2$, or $15$ if you like that better.

• You have forgotten the binomial coefficients and the first one is ${503\choose0}\times (-1)^{503}$ is -1 and multiplied by 2 would be -2 which will give you a remainder of 15 Commented Jun 23, 2017 at 15:31
• I think it was there, just not clear enough, so I used your formula to clarify even further. Commented Jun 23, 2017 at 18:28