2
$\begingroup$

How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.

$\endgroup$
  • $\begingroup$ Use the binary method: $2^{5000} = (2^{2500})^2$, and work from there. You can reduce modulo 10 each step. Also if you get $a^{2 k + 1} = (a^k)^2 \cdot a$. $\endgroup$ – vonbrand Aug 11 at 21:15
5
$\begingroup$

Consider the first few powers of 2:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…

Now take all of those mod 10:

1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4…

Try to solve it yourself, from this, before continuing to read.


There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, if you ever find two powers of two that are congruent (mod 10), the values in between them will form a cycle that loops forever. And it'll always be possible to find such congruent powers, so there'll always be such a cycle with ten or fewer elements in it. (All three of these statements can and should be proven, but those proofs are left as an exercise for the reader.)

In this case, the first such pair of values are 2 and 32. In other words, $2^5 \cong 2^1 \mod 10$. Which means that $2^6 \cong 2^2 \mod 10$, and $2^7 \cong 2^3 \mod 10$, and so on. In general, $2^x \cong 2^y \mod 10$ iff $x \cong y \mod 4$ (for integers $x, y \geq 1$).

So all you have to do now is reduce 5000 mod 4; since we know that $100 \cong 0 \mod 4$, 5000 must also be congruent to zero (and, more relevantly, to four, since our formula only holds for integers ≥ 1—do you see why?). Therefore, $2^{5000} \cong 2^4 \mod 10$. Now you just need to know the first few powers of two, or multiply them out longhand, to find that the answer is $2^{5000} \cong 2^4 \cong 6$.

$\endgroup$
4
$\begingroup$

Write down the first 10 or so powers modulo 10. Do you see a pattern?

$\endgroup$
3
$\begingroup$

$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$

(try to prove it)

$\endgroup$
0
$\begingroup$

And a completely different method, not quite as fast but works for other powers: 5000 = 2*2*2*5*5*5*5. 2 squared = 4, 4 squared = 6, 6square = 6, 6 to the fifth power = 1296 = 6, three times more to the 5th power = 6 (all modulo 10)

Basically raising x to the nth power can be done using at most 2 log n multiplications. (Would be useful for 3146^5000 modulo 8428, for example).

$\endgroup$
  • $\begingroup$ This general, mechanical method is called "exponentiation by squaring" $\endgroup$ – Curtis F Aug 11 at 17:15

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.