Question

The remainder when ${{2}^{2003}}$ is divided by 17 is,
[a]1
[b] 2
[c] 3
[d] None of the above

Answer 1

Hint: Write ${{2}^{2003}}$ as $8\times {{2}^{2000}}$ and use the fact that ${{2}^{4}}=16=17-1$. Hence prove that ${{2}^{2003}}=8\times {{\left( 17-1 \right)}^{500}}$. Use the binomial theorem to find the expansion of the term ${{\left( 17-1 \right)}^{500}}$. Remove all multiples of 17 and hence find the remainder obtained on dividing ${{2}^{2003}}$ by 17. Use the rule of congruences to verify your solution

Complete step-by-step answer:
To find the remainder of ${{2}^{2003}}$ we have to simplify it first. Therefore it can also be written as,
\[\therefore {{2}^{2003}}={{2}^{\left( 2000+3 \right)}}\]
Now to solve further we should know the formula given below,
Formula:
\[{{a}^{m}}\times {{a}^{n}}={{a}^{m+n}}\]
By using the above formula, we can write the equation as,
\[\therefore {{2}^{2003}}={{2}^{2000}}\times {{2}^{3}}\]
Above equation can also be written as,
\[\therefore {{2}^{2003}}={{2}^{4\times 500}}\times {{2}^{3}}\]
As we have to divide ${{2}^{2003}}$ by 17 therefore we have to represent it in the form of 17, and for that, we have to find the power of 2 such that it will give the number nearer to 17.
As we know \[{{2}^{4}}=16\] and it is nearer to 17 therefore we can represent in terms of 17, therefore we will get,
To do that so we have to know the formula given below,
Formula:
\[{{a}^{m\times n}}={{\left( {{a}^{m}} \right)}^{n}}\]
Therefore we can write \[{{2}^{2003}}\] as,
\[\therefore {{2}^{2003}}={{\left( {{2}^{4}} \right)}^{500}}\times {{2}^{3}}\]
If we put \[{{2}^{4}}=16\] in the above equation we will get,
\[\therefore {{2}^{2003}}={{\left( 16 \right)}^{500}}\times {{2}^{3}}\]
Now we can replace 16 as (17 – 1) therefore we will get,
\[\therefore {{2}^{2003}}={{\left( 17-1 \right)}^{500}}\times {{2}^{3}}\]
\[\therefore {{2}^{2003}}=8{{\left( 17-1 \right)}^{500}}\]
Now we will use the formula given below to solve the above equation,
Formula:
\[{{\left( a+b \right)}^{n}}={}^{n}{{C}_{0}}{{a}^{n}}{{b}^{0}}+{}^{n}{{C}_{1}}{{a}^{\left( n-1 \right)}}{{b}^{1}}+{}^{n}{{C}_{2}}{{a}^{\left( n-2 \right)}}{{b}^{2}}+{}^{n}{{C}_{3}}{{a}^{\left( n-3 \right)}}{{b}^{3}}+..............................+{}^{n}{{C}_{(n-1)}}a{{b}^{\left( n-1 \right)}}+{}^{n}{{C}_{n}}{{b}^{n}}\]
By using above formula we can write,
\[\therefore {{2}^{2003}}=8\times \left[ {}^{500}{{C}_{0}}{{17}^{500}}{{\left( -1 \right)}^{0}}+{}^{500}{{C}_{1}}{{17}^{499}}{{\left( -1 \right)}^{1}}+..............................+{}^{500}{{C}_{499}}17{{\left( -1 \right)}^{499}}+{}^{500}{{C}_{500}}{{\left( -1 \right)}^{500}} \right]\]As we know \[{}^{500}{{C}_{0}}=1\], \[{}^{500}{{C}_{500}}=1\], and also the odd powers of -1 gives the value equal to -1 therefore we will get,
\[\therefore {{2}^{2003}}=8\times \underline{{{17}^{500}}+{}^{500}{{C}_{1}}{{17}^{499}}+..............................-{}^{500}{{C}_{499}}17}+1\]
If we observe the underlined part above we come to know that the underlined part is multiple of 17, as we know it will be difficult to write the equation by taking 17 common therefore we will assume it as ‘a’ after we take 17 common.
Therefore if we take 17 common we will get ‘17a’ as we have assumed the product part as ‘a’. Therefore we will get,
\[\therefore {{2}^{2003}}=8\times \left[ 17\times a+1 \right]\]
\[\therefore {{2}^{2003}}=8\times 17a+8\times 1\]
\[\therefore {{2}^{2003}}=8\times 17a+8\]
We know by Euclid's division lemma that if a and b are any two positive integers then there exist unique integers q and r such that $a=bq+r,0\le r\le b-1$, r is known as the remainder of the division of a by b.
Hence by Euclid’s division lemma, we have the remainder obtained if we divide \[{{2}^{2003}}\] by 17 we will get the remainder as 8.

Note: Alternative solution:
We know that if $a\equiv b\left( \bmod m \right)$, then a-b is divisible by m.
Since $16-\left( -1 \right)$ is divisible by 17, we have
$16\equiv -1\left( \bmod 17 \right)$
We know that if $a\equiv b\left( \bmod m \right)$, then ${{a}^{n}}\equiv {{b}^{n}}\left( \bmod m \right)$
Hence, we have
$\begin{align}
  & {{16}^{500}}\equiv {{\left( -1 \right)}^{500}}\left( \bmod m \right) \\
 & \Rightarrow {{2}^{2000}}\equiv 1\left( \bmod m \right) \\
\end{align}$
We know that $a\equiv b\left( \bmod m \right),c\equiv d\left( \bmod m \right)\Rightarrow ac\equiv bd\left( \bmod m \right)$
Also since 8-8 is divisible by 17, we have
$8\equiv 8\left( \bmod 17 \right)$
Hence, we have
$\begin{align}
  & {{2}^{2000}}\times 8\equiv 8\left( \bmod k \right) \\
 & \Rightarrow {{2}^{2003}}\equiv 8\left( \bmod k \right) \\
\end{align}$
Hence, we have
$\begin{align}
  & {{2}^{2003}}-8=17k,k\in \mathbb{Z} \\
 & \Rightarrow {{2}^{2003}}=8+17k \\
\end{align}$
Hence the remainder obtained if we divide \[{{2}^{2003}}\] by 17 we will get the remainder as 8.