Math
Modular Exponentiation Calculator
Enter a base, an exponent, and a modulus to get a^b mod n with the full square-and-multiply table: the exponent in binary, each successive square reduced mod n, and the running product.
Exponents with dozens of digits are fine because nothing larger than n^2 is ever formed. Switch to the inverse mode for a^-1 mod n with the extended Euclidean rows and the Bézout identity, or to the reciprocal mode for the plain multiplicative inverse 1/x.
Whole number, negatives allowed (they are reduced mod n first).
Whole number. Negative exponents use the modular inverse of a.
Positive whole number.
Try an example
Result
Result
—
- Equation
- —
- Exponent in binary
- —
- Check
- —
Student quick launch
Grade planning, algebra checks, and formulas students reach for most.
Study path
Use this calculator with
Follow these when you want the formula behind the answer, a short lesson, or nearby tools in the same topic.
What the modular exponentiation calculator solves
Modular exponentiation asks for the remainder of a^b when divided by n, written a^b mod n. Computing a^b outright is hopeless when b has many digits (4^13 is only 67 million, but 7^1000 has 846 digits), so the trick is to reduce mod n after every multiplication and to use the binary expansion of the The small raised number saying how many times to multiply the base by itself.. This calculator shows that square-and-multiply table, and its two companion operations: the modular inverse and the ordinary The number you get by flipping a fraction; 3/4 becomes 4/3, and 5 becomes 1/5..
Square-and-multiply, step by step
| Bit of 13 = 1101₂ | Power of 4 mod 497 | Multiply in? | Running product |
|---|---|---|---|
| 1 (2^0) | 4^1 = 4 | yes | 4 |
| 0 (2^1) | 4^2 = 16 | no | 4 |
| 1 (2^2) | 4^4 = 256 | yes | 4 × 256 = 1024 ≡ 30 |
| 1 (2^3) | 4^8 = 256^2 = 65536 ≡ 429 | yes | 30 × 429 = 12870 ≡ 445 |
So 4^13 mod 497 = 445. Each row squares the previous power and reduces it, which keeps every intermediate value below n^2. A b-bit exponent needs at most b squarings and b multiplications, which is why RSA can raise numbers to 2048-bit powers in a fraction of a second.
Modular inverse
The inverse of a The remainder left over after dividing one whole number by another. n is the number x with a × x ≡ 1 (mod n). It exists exactly when The largest number that divides evenly into every number in a set.(a, n) = 1. The extended Euclidean algorithm finds it: run Euclid's division steps, then back-substitute to write gcd = a·x + n·y; the The number multiplying a variable, like the 3 in 3x. x, reduced mod n, is the inverse. For 4 mod 497: 497 = 4 × 124 + 1, so 1 = 497 - 4 × 124, giving x = -124 ≡ 373. Negative exponents in the power mode are handled through this inverse: a^-k = (a^-1)^k.
Multiplicative inverse of an ordinary number
Outside modular arithmetic, the multiplicative inverse of x is simply its reciprocal 1/x: the inverse of 0.25 is 4, of 3/4 is 4/3, of -2 1/2 is -2/5. Zero has no inverse. The reciprocal mode computes this exactly as a fraction and a decimal.
How to use it
- Choose the mode: modular power a^b mod n, modular inverse a^-1 mod n, or reciprocal 1/x.
- Enter the numbers. The base may be negative or larger than n; it is reduced first.
- Read the result and the table: for powers, one row per binary digit of the exponent; for inverses, one row per Euclidean division.
- Open Show the work for the same steps written as congruences you can copy into homework.
How to read the answer
The result is always between 0 and n - 1. In the power table, the running product only changes on rows where the exponent bit is 1, and the final running product is the answer. An inverse result x satisfies a × x = (multiple of n) + 1; if gcd(a, n) is not 1 there is no inverse and the page says so. The reciprocal is exact as a fraction; its decimal may repeat.
Common mistakes and edge cases
- Computing a^b in full and then reducing: overflow or a 800-digit number. Reduce after every multiplication.
- Expecting an inverse when gcd(a, n) > 1: 6 has no inverse mod 9.
- Forgetting to reduce a negative Bézout coefficient into 0 … n - 1: -124 mod 497 = 373.
- Reading the binary digits in the wrong order; the table starts from the least significant bit (2^0).
- Confusing the modular inverse (a number mod n) with the reciprocal 1/a (a fraction).
Worked examples
4^13 mod 497
Classic textbook example: 445.
Result
445
Huge exponent
7^1000 mod 13 without computing 7^1000.
Result
9
Negative base
(-3)^5 = -243 = 7 × (-35) + 2, so the answer is 2.
Result
2
Zero exponent
a^0 = 1.
Result
1
Negative exponent
3^-1 mod 11 = 4, so 3^-2 ≡ 16 ≡ 5.
Result
5
Modular inverse of 4 mod 497
4 × 373 = 1492 = 3 × 497 + 1.
Result
373
No inverse
gcd(6, 9) = 3.
Result
Error
Reciprocal of 0.25
1/0.25 = 4.
Result
4
Reciprocal of a mixed number
-2 1/2 = -5/2 → -2/5.
Result
-2/5
Reciprocal of zero
Undefined.
Result
Error
Frequently asked questions
What is modular exponentiation?+
Finding the remainder of a power: a^b mod n. For example 4^13 mod 497 = 445 because 4^13 = 67,108,864 = 135,027 × 497 + 445.
How does square-and-multiply work?+
Write the exponent in binary. Starting from the base, square repeatedly (reducing mod n each time) to get a^1, a^2, a^4, a^8, …; then multiply together the powers whose bits are 1. 13 = 8 + 4 + 1, so 4^13 = 4^8 × 4^4 × 4^1.
Why not compute the power and then take the remainder?+
Because the power is astronomically large: 7^1000 has 846 digits. Reducing after each step keeps every number below n^2 and gives the same answer, since (a × b) mod n = ((a mod n)(b mod n)) mod n.
What is a modular inverse?+
The number x with a × x ≡ 1 (mod n). 4^-1 mod 497 = 373 because 4 × 373 = 1492 = 3 × 497 + 1. It exists only when gcd(a, n) = 1.
How do I find a modular inverse by hand?+
Run the extended Euclidean algorithm on a and n to write 1 = a × x + n × y, then reduce x mod n. The inverse mode shows every division row.
What is the multiplicative inverse of a number?+
Its reciprocal 1/x, the number that multiplies it to give 1: the inverse of 3/4 is 4/3, of 0.2 is 5. Zero has none.
Where is modular exponentiation used?+
RSA encryption and signatures, Diffie–Hellman key exchange, primality tests like Miller–Rabin, and hash-based check digits all raise numbers to huge powers modulo n.
About this calculator
- Written by
- mathcheck editorial team
- Last reviewed
- September 4, 2026
Method
- Uses the values entered by the user and stable formulas documented on the page.
References
- NIST FIPS 186-5, Digital Signature Standard, Appendix B (modular exponentiation and inverses)
- Knuth, The Art of Computer Programming, Vol. 2, §4.6.3 Evaluation of Powers — Binary (square-and-multiply) exponentiation.
Related calculators
Modulo Calculator
Find a mod n for integers, negative numbers, and decimals with the quotient, remainder, division equation, congruence class, clock visual, and a clear explanation of floored vs truncated remainders.
Exponent Calculator
Calculate powers with positive, negative, and decimal exponents while showing the exponent rule used.
GCF Calculator
Find the greatest common factor (GCF, also called GCD or HCF) of any list of whole numbers with three worked methods: listing factors, the prime-factorization table, and Euclid's division algorithm.
Prime Number Calculator
Test whether a number is prime (up to 24 digits, exactly), see the trial-division or Miller–Rabin reasoning, get the prime factorization for composites, the nearest primes above and below, or list all primes in a range.
Remainder Calculator
Divide two whole numbers and get the quotient and remainder, the check equation a = b × q + r, the mixed-number, fraction, and decimal forms of the same division, and both sign conventions for negatives.
Reciprocal Calculator
Find the reciprocal (multiplicative inverse) of an integer, decimal, fraction, or mixed number as an exact fraction, a mixed number, and a decimal, with the conversion steps and the check x × 1/x = 1.
Last updated: September 4, 2026