How can we calculate remainder when $3^{2014}$ is divided by $10,000$?

Can we solve it using the binomial theorem?

My solution: We can write $3^{2014} = 9^{2007} = -(1-10)^{2007}$. Now,

$$(1-10)^{2007} = \binom{2007}{0}-\binom{2007}{1}(10)+\binom{2007}{2}(10)^2-\binom{2007}{3}(10)^3+M(10,000)$$

Where $M(10,000) = $ Multiple of $10,000$. So:

$$(1-10)^{2007} = 1-2007\cdot (10)+(2007)\cdot (1003)(10)^2-(667)\cdot (1003)\cdot (2005)\cdot(10)^3+M(10,000)$$

$$-(1-10)^{1007} = -1+20070-(20130210)+(13413470050)+M(10,000)$$

But this answer is not right. Please help me.

Is there is any better method than that? If so, please explain it to me.

  • 6
    $\begingroup$ Note that $2014/2=1007$. $\endgroup$ – André Nicolas May 28 '14 at 17:26
  • $\begingroup$ Check again the division $2007/3$. $\endgroup$ – LutzL May 28 '14 at 17:31

Your Binomial Theorem solution is fine, apart from minor arithmetical glitches.

Or else note that $10000=2^4\cdot 5^4$. We have $\varphi(2^4)=8$ and $\varphi(5^4)=(4)(125)$. Each of these divides $2000$, so $3^{2000}\equiv 1\pmod{10000}$.

You can also find that $3^{2000}\equiv 1\pmod{10000}$ by your Binomial Theorem method, with much reduced chance of an arithmetical error.

So now we are interested in the remainder when $3^{14}$ is divided by $10000$. This is straightforward by calculator, or even by hand.

Remark: We carry out the calculation as you intended to do it. Modulo $10000$, our number is congruent to $$-\left(1-\binom{1007}{1}(10)+\binom{1007}{2}(100)-\binom{1007}{3}(1000) \right).$$ Now calculate. The number $\binom{1007}{3}$ is divisible by $5$ but not by $10$, so modulo $10000$ that term is congruent to $5000$. We have $(10)(1007)\equiv 70\pmod{10000}$ and $100\binom{1007}{2}=(100)(1007)(503)\equiv 2100\pmod{10000}$, so we get $-(1-70+2100-5000)$, that is, $2969$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.