3

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.

senshin
  • 503
juantheron
  • 53,015

1 Answers1

2

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$.

André Nicolas
  • 507,029