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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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