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 entered3200 mod 133^{200} \bmod 13

3200 mod 13=9\displaystyle 3^{200} \bmod 13 = 9

Congruence

3200≡9(mod13)\displaystyle 3^{200} \equiv 9 \pmod{13}
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 8 bits.

    200=110010002200 = \mathrm{11001000}_{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 1313 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

    31≡3(mod13)33≡32×3=27≡1(mod13)36≡12=1(mod13)312≡12=1(mod13)325≡12×3=3(mod13)350≡32=9(mod13)3100≡92=81≡3(mod13)3200≡32=9(mod13)\begin{array}{l} 3^{1} \equiv 3 \pmod{13} \\ 3^{3} \equiv 3^{2} \times 3 = 27 \equiv 1 \pmod{13} \\ 3^{6} \equiv 1^{2} = 1 \pmod{13} \\ 3^{12} \equiv 1^{2} = 1 \pmod{13} \\ 3^{25} \equiv 1^{2} \times 3 = 3 \pmod{13} \\ 3^{50} \equiv 3^{2} = 9 \pmod{13} \\ 3^{100} \equiv 9^{2} = 81 \equiv 3 \pmod{13} \\ 3^{200} \equiv 3^{2} = 9 \pmod{13} \end{array}
  3. Result

    So 3200≡9(mod13)3^{200} \equiv 9 \pmod{13}, that is, the remainder is 99.

Worked examples