Find the remainder when 6701^83 is divided by 1000.

How would I use the binomial theorem to get the answer of this question?

Guest Mar 10, 2019

edited by
Guest
Mar 10, 2019

#1**+1 **

\(6701^{83} = \sum \limits_{k=0}^{83} ~\dbinom{83}{k} (6000)^{k}(701)^{83-k}\\ \text{It should be clear that all terms but 1, }k=0 \text{ are divisible by }1000\\ \text{we are then left with }\\ (701)^{83} = \sum \limits_{k=0}^{83}\dbinom{83}{k}(700)^k\\ \text{here there are two terms that are not divisible by }1000,~k=0,1\\ (701)^{83}\pmod{1000} = \\ 1+83(700) \pmod{1000} = \\ 1 + (80+3)(700) \pmod{1000}= \\ 1+ 56000+ 2100 \pmod{1000} = \\ 2101 \pmod{1000} = 101\)

.Rom Mar 10, 2019

#2**0 **

Binomial Expansion approach

(6701)^83 =

(6700 + 1)^83 = 6700^83 + C(83,1)*6700^82 + ...+ C(83,81)*6700^2 + C(83,82)*6700 + 1

Note that every term in red will have at least 4 trailing zeros, so each of these terms is divisible by 1000

So....we only need consider the last two terms

C(83, 82) * 6700 + 1 =

83 * (6700) + 1 =

(80 + 3) * (6700) + 1 =

80*6700 + 3*6700 + 1

The first term will have 3 trailing zeros, so....it is divisible by 1000....and

3 * 6700 + 1 = 20100 + 1 = 20(1000) + 100 + 1

So we have left

[ 100 + 1 ] / 1000 ⇒ remainder 101

CPhill Mar 11, 2019