Solve any maths problem

Equations, derivatives, integrals, matrices, triangles, primes, statistics — or a word problem the tutor breaks into parts.

Number-Theory · Modular-Arithmetic

5^20 mod 21

5,\ 20,\ 21

Step by step

  1. 5^{20} \bmod 21

    Never compute the huge power. Reduce after every multiplication (repeated squaring).

  2. 5 \equiv 5 \pmod{21}

    Reduce the base first.

  3. 20 = 10100_2

    Write the exponent in binary: 5 squarings at most.

  4. 5^2 \equiv 4 \pmod{21}

    Square the running power.

  5. 4^2 \equiv 16 \pmod{21}

    Square the running power.

  6. r \leftarrow r \cdot 16 \equiv 16 \pmod{21}

    This bit is 1: multiply the result by the current power.

  7. 16^2 \equiv 4 \pmod{21}

    Square the running power.

  8. 4^2 \equiv 16 \pmod{21}

    Square the running power.

  9. r \leftarrow r \cdot 16 \equiv 4 \pmod{21}

    This bit is 1: multiply the result by the current power.

  10. 5^{20} \equiv 4 \pmod{21}

    Done.

Reveal the answer
5^{20} \bmod 21 = 4