Modular Arithmetic
Modular exponentiation, modular inverse, gcd, lcm.
Overview
The Modular Arithmetic calculator handles the four operations you reach for in number theory and cryptography: modular exponentiation a^b mod n, modular inverse a^-1 mod n, GCD via the Euclidean algorithm and LCM. It uses arbitrary-precision integers internally so you can plug in cryptography-sized values.
It is built for students learning RSA, security engineers checking back-of-envelope key arithmetic, contest programmers and anyone working with cyclic groups. Naive pow(a, b) % n overflows for big inputs; this tool's modular exponentiation does not.
How it works
Modular exponentiation uses square-and-multiply: write the exponent in binary and, for each bit, square the running result and optionally multiply by the base, reducing modulo n after every step. This keeps intermediate values bounded by n^2.
Modular inverse uses the extended Euclidean algorithm: find integers x, y such that a * x + n * y = gcd(a, n). If gcd is 1, x mod n is the inverse; otherwise no inverse exists. GCD and LCM share the same Euclidean machinery.
Examples
2^10 mod 1000 → 24
3^644 mod 645 → 36
inverse of 7 mod 26 → 15 (since 7 * 15 = 105 = 4*26 + 1)
gcd(252, 105) = 21, lcm(252, 105) = 1260
FAQ
Why is square-and-multiply faster than naive exponentiation?
It uses O(log b) multiplications instead of O(b). For a 2048-bit exponent the difference is between a few thousand operations and an impossible number.
When does a modular inverse exist?
a^-1 mod n exists if and only if gcd(a, n) = 1. If they share a common factor, no inverse exists.
Is mod the same as remainder?
In maths, mod always returns a non-negative result. In many programming languages % follows the sign of the dividend. The calculator returns the mathematical (non-negative) remainder.
How is this used in RSA?
RSA encrypts and decrypts via modular exponentiation c = m^e mod n and m = c^d mod n, where d is the modular inverse of e modulo Euler's totient.
Can I work modulo a non-prime?
Yes for exponentiation, gcd and lcm. Inverses exist only when gcd is 1.