# Tag Info

0

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

5

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

3

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

4

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

2

It's even a bit simpler, namely both: a <u b == (a ^ m) <s (b ^ m), and, a <s b == (a ^ m) <u (b ^ m) Where m is the mask with the sign bit set. I don't have a formal proof for that, but the image below shows what is happening. The top row shows the "unsigned order" of the number line, chopped in half, with the first part having a 0 in the top ...

Top 50 recent answers are included