About the Modular Exponentiation Calculator
This modular exponentiation calculator computes a^b mod n — the remainder when a raised to the power b is divided by n — exactly, even when a, b and n have hundreds of digits. Computing a^b first and then reducing is impossible for large exponents (2^1000 alone has 302 digits), so the calculator uses fast binary exponentiation, reducing modulo n after every step so numbers never grow beyond n².
It is built for number theory and cryptography students working through RSA, Diffie–Hellman or Fermat primality tests, competitive programmers checking answers modulo 1,000,000,007, and anyone verifying a "power mod" homework problem. The step table shows the exponent in binary and how each squaring and multiplication builds the answer.
Negative exponents are supported when the base has a modular inverse: a^(−b) mod n means (a⁻¹)^b mod n, which exists only when gcd(a, n) = 1. Negative bases are reduced into the range 0 to n − 1 first. All arithmetic uses exact big integers, so results are never rounded.
How to use the modular exponentiation calculator
- 1Enter the base a — any whole number, positive or negative.
- 2Enter the exponent b; use a negative value to raise the modular inverse.
- 3Enter the modulus n (a positive whole number, e.g. 1000000007).
- 4Read a^b mod n, then follow the step table to see each squaring and multiplication.
Formula and method
Fast modular exponentiation (square-and-multiply) writes the exponent in binary. Starting from a mod n, it repeatedly squares to get a², a⁴, a⁸, … modulo n, and multiplies the running result by a^(2ⁱ) whenever bit i of the exponent is 1. Because every intermediate product is reduced mod n, numbers stay smaller than n², and the work grows with the number of bits (about log₂ b) rather than with b itself.
For a negative exponent the calculator first finds the modular inverse a⁻¹ with the extended Euclidean algorithm — it exists only when gcd(a, n) = 1 — and then computes (a⁻¹)^|b| mod n. All arithmetic uses arbitrary-precision integers, so results are exact.
- a
- Base (reduced into 0 … n − 1)
- b
- Exponent; bᵢ is its i-th binary digit
- n
- Modulus (positive integer)
- φ(n)
- Euler’s totient, used in Euler’s theorem a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1
Worked examples
4^13 mod 497
13 = 1101 in binary, so 4^13 = 4^8 · 4^4 · 4^1. Mod 497: 4^2 = 16, 4^4 = 256, 4^8 = 256² mod 497 = 429. Then 4 · 256 = 1024 ≡ 30, and 30 · 429 = 12,870 ≡ 445. That took 3 squarings and 2 multiplications.
2^1000 mod 1,000,000,007
2^1000 has 302 digits, but binary exponentiation needs only 10 bits’ worth of squarings. Reducing modulo the prime 1,000,000,007 at every step gives 688,423,210.
Negative exponent: 5^−3 mod 13
Since 5 · 8 = 40 ≡ 1 (mod 13), the inverse of 5 is 8. Then 8³ = 512 = 39 · 13 + 5, so 5^−3 ≡ 5 (mod 13). Check: 5^3 = 125 ≡ 8 and 8 · 5 = 40 ≡ 1.
Carmichael number fooling Fermat: 7^560 mod 561
561 = 3 · 11 · 17 is composite, yet 7^560 ≡ 1 (mod 561), just as Fermat’s little theorem would predict for a prime. 561 is the smallest Carmichael number, which is why stronger tests such as Miller–Rabin exist.
Frequently asked questions
How do you calculate a^b mod n by hand?+
Write b in binary, compute a, a², a⁴, a⁸ … by repeated squaring, reducing mod n each time, and multiply together the powers whose binary digit is 1, again reducing mod n after every multiplication.
Why not just compute a^b and then take the remainder?+
a^b becomes astronomically large: 2^1000 has 302 digits and RSA exponents are often hundreds of digits long. Reducing at each step keeps every number below n², so the calculation stays fast and exact.
What does a negative exponent mean in modular arithmetic?+
a^(−b) mod n means (a⁻¹)^b mod n, where a⁻¹ is the number that multiplies with a to give 1 mod n. It exists only when a and n share no common factor, i.e. gcd(a, n) = 1.
How is modular exponentiation used in RSA?+
RSA encryption computes c = m^e mod n and decryption computes m = c^d mod n, where n is the product of two large primes. Both steps are modular exponentiation with very large numbers, done by square-and-multiply.
What is Fermat’s little theorem?+
If p is prime and a is not a multiple of p, then a^(p−1) ≡ 1 (mod p). It lets you reduce huge exponents modulo p − 1, and it underlies the Fermat primality test — though Carmichael numbers such as 561 can pass it while being composite.
How many multiplications does fast exponentiation need?+
About log₂ b squarings plus one multiplication for each 1-bit in b, at most roughly 2·log₂ b in total. For a 2048-bit exponent that is about 3,000 operations instead of an impossible 2^2048.