Modular Exponentiation Calculator

Enter a base, an exponent and a modulus to find the remainder of the power.

Any whole number, positive or negative.

A whole number, 0 or more.

A whole number other than 0.

Try

Result

You entered210 mod 10002^{10} \bmod 1000

210 mod 1000=24\displaystyle 2^{10} \bmod 1000 = 24

Congruence

210≡24(mod1000)\displaystyle 2^{10} \equiv 24 \pmod{1000}
Show the work
  1. Binary form of the exponent

    The bits of the exponent say which moves to make. Read them from left to right: every bit after the first means square the running result, and a bit that is 1 also means multiply by the base. The exponent has 4 bits.

    10=1010210 = \mathrm{1010}_{2}
  2. Square and multiply

    Each line doubles the exponent by squaring, adds one more by multiplying by the base when the bit is 1, and then keeps only the remainder mod 10001000 so the numbers stay small.

    Using a2k=(ak)2,a2k+1=(ak)2×aa^{2k} = \left(a^{k}\right)^{2}, \quad a^{2k+1} = \left(a^{k}\right)^{2} \times a

    21≡2(mod1000)22≡22=4(mod1000)25≡42×2=32(mod1000)210≡322=1024≡24(mod1000)\begin{array}{l} 2^{1} \equiv 2 \pmod{1000} \\ 2^{2} \equiv 2^{2} = 4 \pmod{1000} \\ 2^{5} \equiv 4^{2} \times 2 = 32 \pmod{1000} \\ 2^{10} \equiv 32^{2} = 1024 \equiv 24 \pmod{1000} \end{array}
  3. Result

    So 210≡24(mod1000)2^{10} \equiv 24 \pmod{1000}, that is, the remainder is 2424.

Worked examples