I-ScrabbleName

Ii-equations, i-derivates, i-integrals, i-matrices, i-triangles, i-primes, i-statistics — okanye ingxaki yegama ufundi uyamqula iinkalo.

Number-Theory · Modular-Arithmetic

4^3 mod 5

4,\ 3,\ 5

Inyathelo ngenyathelo

  1. 4^{3} \bmod 5

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

  2. 4 \equiv 4 \pmod{5}

    Reduce the base first.

  3. 3 = 11_2

    Write the exponent in binary: 2 squarings at most.

  4. r \leftarrow r \cdot 4 \equiv 4 \pmod{5}

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

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

    Square the running power.

  6. r \leftarrow r \cdot 1 \equiv 4 \pmod{5}

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

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

    Done.

Bonisa impendulo
4^{3} \bmod 5 = 4