Ҳар қандай математика муаммосини ҳал қилиш

Қадамма-қадам

1. 2^{5} \bmod 5

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

2. 2 \equiv 2 \pmod{5}

   Reduce the base first.

3. 5 = 101_2

   Write the exponent in binary: 3 squarings at most.

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

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

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

   Square the running power.

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

   Square the running power.

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

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

8. 2^{5} \equiv 2 \pmod{5}

   Done.

Жавобни кўрсатиш

2^{5} \bmod 5 = 2