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 entered7123456789 mod 10000037^{123456789} \bmod 1000003

7123456789 mod 1000003=568863\displaystyle 7^{123456789} \bmod 1000003 = 568863

Congruence

7123456789≡568863(mod1000003)\displaystyle 7^{123456789} \equiv 568863 \pmod{1000003}
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 27 bits.

    123456789=1110101101111001101000101012123456789 = \mathrm{111010110111100110100010101}_{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 10000031000003 so the numbers stay small. The table stops after 20 lines; the same two moves carry on for the rest of the bits.

    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

    71≡7(mod1000003)73≡72×7=343(mod1000003)77≡3432×7=823543(mod1000003)714≡8235432=678223072849≡38186(mod1000003)729≡381862×7=10207194172≡163551(mod1000003)758≡1635512=26748929601≡849357(mod1000003)7117≡8493572×7=5049851194143≡44635(mod1000003)7235≡446352×7=13945982575≡940740(mod1000003)7470≡9407402=884991747600≡92633(mod1000003)7941≡926332×7=60066108823≡928628(mod1000003)71883≡9286282×7=6036449736688≡627395(mod1000003)73767≡6273952×7=2755371402175≡136086(mod1000003)77535≡1360862×7=129635795772≡406867(mod1000003)715070≡4068672=165540755689≡259069(mod1000003)730140≡2590692=67116746761≡545413(mod1000003)760281≡5454132×7=2082327383983≡137020(mod1000003)7120563≡1370202×7=131421362800≡968540(mod1000003)7241126≡9685402=938069731600≡917402(mod1000003)7482253≡9174022×7=5891385007228≡333127(mod1000003)7964506≡3331272=110973598129≡265210(mod1000003)⋮\begin{array}{l} 7^{1} \equiv 7 \pmod{1000003} \\ 7^{3} \equiv 7^{2} \times 7 = 343 \pmod{1000003} \\ 7^{7} \equiv 343^{2} \times 7 = 823543 \pmod{1000003} \\ 7^{14} \equiv 823543^{2} = 678223072849 \equiv 38186 \pmod{1000003} \\ 7^{29} \equiv 38186^{2} \times 7 = 10207194172 \equiv 163551 \pmod{1000003} \\ 7^{58} \equiv 163551^{2} = 26748929601 \equiv 849357 \pmod{1000003} \\ 7^{117} \equiv 849357^{2} \times 7 = 5049851194143 \equiv 44635 \pmod{1000003} \\ 7^{235} \equiv 44635^{2} \times 7 = 13945982575 \equiv 940740 \pmod{1000003} \\ 7^{470} \equiv 940740^{2} = 884991747600 \equiv 92633 \pmod{1000003} \\ 7^{941} \equiv 92633^{2} \times 7 = 60066108823 \equiv 928628 \pmod{1000003} \\ 7^{1883} \equiv 928628^{2} \times 7 = 6036449736688 \equiv 627395 \pmod{1000003} \\ 7^{3767} \equiv 627395^{2} \times 7 = 2755371402175 \equiv 136086 \pmod{1000003} \\ 7^{7535} \equiv 136086^{2} \times 7 = 129635795772 \equiv 406867 \pmod{1000003} \\ 7^{15070} \equiv 406867^{2} = 165540755689 \equiv 259069 \pmod{1000003} \\ 7^{30140} \equiv 259069^{2} = 67116746761 \equiv 545413 \pmod{1000003} \\ 7^{60281} \equiv 545413^{2} \times 7 = 2082327383983 \equiv 137020 \pmod{1000003} \\ 7^{120563} \equiv 137020^{2} \times 7 = 131421362800 \equiv 968540 \pmod{1000003} \\ 7^{241126} \equiv 968540^{2} = 938069731600 \equiv 917402 \pmod{1000003} \\ 7^{482253} \equiv 917402^{2} \times 7 = 5891385007228 \equiv 333127 \pmod{1000003} \\ 7^{964506} \equiv 333127^{2} = 110973598129 \equiv 265210 \pmod{1000003} \\ \vdots \end{array}
  3. Result

    So 7123456789≡568863(mod1000003)7^{123456789} \equiv 568863 \pmod{1000003}, that is, the remainder is 568863568863.

Worked examples