Vyriešte akýkoľvek matematický problém

Rovnice, derivácie, integrály, matice, trojuholníky, prvočísla, štatistiky alebo slovný problém, ktorý učiteľ rozdelí na časti.

Number-Theory · Modular-Arithmetic

4^3 mod 5

4,\ 3,\ 5

Krok za krokom

  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.

Odhaliť odpoveď
4^{3} \bmod 5 = 4