Question

When ${{2}^{256}}$ was divided by 17 the remainder is,
A.1
B. 2
C. 3
D. 4

Answer 1

Hint: We can write the given dividend as ${{2}^{256}}={{\left( 17-1 \right)}^{64}}$. We expand it binomially and see that all the terms except that last term ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ is a multiple of 17 and will leave the reminder 0 because 17 is factor of each of them. So the remainder we obtain we divide the last term ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ by 17 is also the remainder of ${{2}^{256}}$.

Complete step-by-step solution
We know that the binomial expansion of ${{\left( x+y \right)}^{n}}$ can written as
\[{{\left( x+y \right)}^{n}}={}^{n}{{C}_{o}}{{x}^{n}}{{y}^{0}}+{}^{n}{{C}_{1}}{{x}^{n-1}}{{y}^{1}}+{}^{n}{{C}_{2}}{{x}^{n-2}}{{y}^{2}}+...+{}^{n}{{C}_{n-1}}{{x}^{0}}{{y}^{n-1}}+{}^{n}{{C}_{n}}{{x}^{0}}{{y}^{n}}\]
Here $n$ is any non-negative integer, $x,y$ are any real numbers and ${}^{n}{{C}_{0}},{}^{n}{{C}_{1}},...,{}^{n}{{C}_{n}}$ are positive integers called binomial coefficients. The binomial coefficients are obtained from the formula for some $r < n$ as
\[{}^{n}{{C}_{r}}=\dfrac{n!}{n!\left( n-r \right)!}\]
We know that ${}^{n}{{C}_{0}}={}^{n}{{C}_{n}}=1$ We can also write the binomial expansion in summation form as
\[{{\left( x+y \right)}^{n}}=\sum\limits_{k=0}^{n}{{}^{n}{{C}_{k}}}{{x}^{k}}{{y}^{n-k}}\]
We are given the dividend ${{2}^{256}}$ and divisor 17 in the question. We can write the dividend ${{2}^{256}}$ as ,
\[{{2}^{256}}={{2}^{4\times 64}}={{\left( {{2}^{4}} \right)}^{64}}={{16}^{64}}={{\left( 17-1 \right)}^{64}}={{\left\{ 17+\left( -1 \right) \right\}}^{n}}\]
We expand the result obtained binomially for $x=1,y=-1,n=64$. We have,
\[\begin{align}
  & \Rightarrow {{2}^{256}}={{\left\{ 17+\left( -1 \right) \right\}}^{64}}={}^{64}{{C}_{0}}{{17}^{64}}{{\left( -1 \right)}^{0}}+{}^{64}{{C}_{1}}{{17}^{63}}{{\left( -1 \right)}^{1}}+{}^{64}{{C}_{2}}{{17}^{62}}{{\left( -1 \right)}^{2}} \\
 & ...+{}^{64}{{C}_{63}}{{17}^{1}}{{\left( -1 \right)}^{63}}+{}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}...\left( 1 \right) \\
\end{align}\]
We observe in the above expansion that all the terms are multiples of 17 except the term ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ because the binomial coefficients ${}^{64}{{C}_{0}},{}^{64}{{C}_{1}},...,{}^{64}{{C}_{64}}$ are positive integers and in all the terms 17 or the exponent of 17 exist. If we divide the expansion (1) by 17 all the terms will leave remainder 0 except ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$. We can write the expansion for some integers ${{m}_{0}},{{m}_{1}},...{{m}_{63}}$ as
\[\Rightarrow {{2}^{256}}=17{{m}_{0}}+17{{m}_{1}}+...17{{m}_{63}}+{}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}\]
Here we know that the sum of integers is an integer because of the closer property of the set of integers. So let us denote the $m={{m}_{0}}+{{m}_{1}}+...{{m}_{63}}$. We use it in the next step and have,
\[\begin{align}
  & \Rightarrow {{2}^{256}}=17\left( {{m}_{0}}+{{m}_{1}}+...+{{m}_{63}} \right)+{}^{64}{{C}_{0}}{{17}^{0}}{{\left( -1 \right)}^{64}} \\
 & \Rightarrow {{2}^{256}}=17m+{}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}} \\
\end{align}\]
Let us simplify the only term ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ that is not exactly divisible by17. We have
\[{}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}=1\cdot 1\cdot 1=1\left( \because {}^{64}{{C}_{64}}=1 \right)\]
${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}=1$
When we divide the term ${}^{64}{{C}_{64}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ by 17 the term will leave the remainder 1 and hence when we divide ${{2}^{256}}=17m+{}^{64}{{C}_{0}}{{17}^{0}}{{\left( -1 \right)}^{64}}$ by 17 it will also leave the remainder 1. So when we divide ${{2}^{256}}$ will leave the remainder.\[\]

Note: We can alternatively solve using a modular arithmetic theorem called Fermat’s little theorem . We write the congruent modulo function as $a\equiv b\left( \left| p \right| \right)$ when $a$ leave the remainder $b$ divided by $p.$ We know from Fermat’s little theorem that for $a\in N$ and prime $p$, ${{a}^{p-1}}\equiv 1\left( \left| p \right| \right)$. We take $p=17,a=2$ and have ${{\left( {{2}^{17-1}} \right)}^{16}}\equiv 1\left( \left| p \right| \right)$ to conclude that ${{2}^{256}}$ will leave the remainder 1.