maths.free › Number Theory › Modular arithmetic

Modular arithmetic

Remainders, congruences, fast powers and modular inverses.

Arithmetic on a clock: only the remainder matters. Huge powers are tamed by reducing after every multiplication (repeated squaring), and a modular inverse — the number that undoes multiplication — comes from the extended Euclidean algorithm. This is the engine behind RSA encryption.

Worked example: 3^100 mod 7

Number-Theory · Modular-Arithmetic

3^100 mod 7

3,\ 100,\ 7

Step by step

  1. 3^{100} \bmod 7

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

  2. 3 \equiv 3 \pmod{7}

    Reduce the base first.

  3. 100 = 1100100_2

    Write the exponent in binary: 7 squarings at most.

  4. 3^2 \equiv 2 \pmod{7}

    Square the running power.

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

    Square the running power.

  6. r \leftarrow r \cdot 4 \equiv 4 \pmod{7}

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

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

    Square the running power.

  8. 2^2 \equiv 4 \pmod{7}

    Square the running power.

  9. 4^2 \equiv 2 \pmod{7}

    Square the running power.

  10. r \leftarrow r \cdot 2 \equiv 1 \pmod{7}

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

  11. 2^2 \equiv 4 \pmod{7}

    Square the running power.

  12. r \leftarrow r \cdot 4 \equiv 4 \pmod{7}

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

  13. 3^{100} \equiv 4 \pmod{7}

    Done.

Reveal the answer
3^{100} \bmod 7 = 4

Try your own

More in Number Theory

Prime factorisationPrime numbersGCD and LCMDivisorsSequencesNumber bases