Question

Find the remainder when $ {2^{47}} $ is divided by $ 7 $ .

Answer 1

Hint: We have to proceed with the binomial approach here or we can also go with the simple approach if we need an approximate answer (or if the options are given). We can see that powers of two end with 2,4,8,6,2 and so on i.e. the units place gets repeated after every 4th power. So, seeing this pattern, we can determine the units place of $ {2^{47}} $ as 8. So the remainder on dividing by 7 can be either 4,0,2 etc. But to be sure we have to use binomial theorem.
Formula used-
The formula used here is the expansion of binomial series. The Binomial Theorem states that, where n is a positive integer:
 $
  {\left( {a + b} \right)^n} = \sum\limits_{k = 0}^n {\left( {_k^n} \right){a^{n - k}}{b^k}} = \sum\limits_{k = 0}^n {\left( {_k^n} \right){a^k}{b^{n - k}}} \\
   \Rightarrow {\left( {a + b} \right)^n} = {a^n} + {}^n{C_1}{a^{n - 1}}b + {}^n{C_2}{a^{n - 2}}{b^2} + ... + {}^n{C_{n - 1}}a{b^{n - 1}} + {b^n} \\
  $

Complete step-by-step answer:
Here we have to use the binomial theorem so as to find the remainder when $ {2^{47}} $ is divided by $ 7 $ .
The Binomial Theorem states that, where n is a positive integer:
 $
  {\left( {a + b} \right)^n} = \sum\limits_{k = 0}^n {\left( {_k^n} \right){a^{n - k}}{b^k}} = \sum\limits_{k = 0}^n {\left( {_k^n} \right){a^k}{b^{n - k}}} \\
   \Rightarrow {\left( {a + b} \right)^n} = {a^n} + {}^n{C_1}{a^{n - 1}}b + {}^n{C_2}{a^{n - 2}}{b^2} + ... + {}^n{C_{n - 1}}a{b^{n - 1}} + {b^n} \;
  $
So, here let a+b=2 and n=47 and we assume it to be divisible by 7,
 $ {\left( 2 \right)^{47}} = x\left( {\bmod 7} \right) $
where x is the remainder on dividing the L.H.S by 7. The notation (mod 7) denotes that the number is being divided by 7.
 $
  \left( {{2^2}} \right)\left( {{2^{45}}} \right) = x\left( {\bmod 7} \right) \\
   \Rightarrow 4.\left( {{2^{3 \times 15}}} \right) = x\left( {\bmod 7} \right) \\
   \Rightarrow 4.{\left( {{2^3}} \right)^{15}} = x\left( {\bmod 7} \right) \\
   \Rightarrow 4.{\left( 8 \right)^{15}} = x\left( {\bmod 7} \right) \\
   \Rightarrow 4.{\left( {7 + 1} \right)^{15}} = x\left( {\bmod 7} \right) \;
  $
Here, we have written powers of 2 in such a way that we have used the least integer that can be expressed as a sum of 7 with another integer i.e. 8=7+1. Why this is done will be understood in further steps. Now, we are expanding $ {\left( {7 + 1} \right)^{15}} $ using binomial theorem.
 $
   \Rightarrow 4.\left( {{7^{15}} + {}^{15}{C_1}{7^{14}}.1 + {}^{15}{C_2}{7^{13}}{{.1}^2} + ... + {}^{15}{C_{14}}{{7.1}^{14}} + {1^{15}}} \right) = x\left( {\bmod 7} \right) \\
   \Rightarrow {4.7^{15}} + 4.{}^{15}{C_1}{7^{14}}.1 + 4.{}^{15}{C_2}{7^{13}}{.1^2} + ... + 4.{}^{15}{C_{14}}{7.1^{14}} + 4 = x\left( {\bmod 7} \right) \\
  $
Now, on the L.H.S, we can see that from the first to the second last term we can take 7 as common and let the remaining term in the bracket be $ \lambda $
 $
   \Rightarrow 7\left( {{{4.7}^{14}} + 4.{}^{15}{C_1}{7^{13}}.1 + 4.{}^{15}{C_2}{7^{12}}{{.1}^2} + ... + 4.{}^{15}{C_{14}}{1^{14}}} \right) + 4 = x\left( {\bmod 7} \right) \\
   \Rightarrow 7\lambda + 4 = x\left( {\bmod 7} \right) \\
   \Rightarrow x = 4 \;
  $
Now because the first term is a multiple of 7, therefore the remainder will be 0, so the extra 4 would be left as remainder on dividing the whole term by 7.
Therefore, the correct answer on dividing $ {2^{47}} $ by $ 7 $ is 4
So, the correct answer is “4”.

Note: Here we see why it is necessary to break powers of 2 in such a way that they become powers of sum of (7+1), so that only one constant term remains to be of relevance for finding the remainder. Also, we can only break it with a sum or difference of 1. For example, if we break down 16 as 14+2 and then expand it we’ll get a term as $ {2^{11}} $ or something which again isn’t possible to solve and find remainder but for 1, any power will still be 1.