Modular Arithmetic Calculator | Modular Inverse, CRT & Power Mod
Perform all core modular arithmetic operations with full step-by-step working. Computes (a op b) mod n, finds modular inverses using the Extended Euclidean Algorithm, solves two-congruence systems via the Chinese Remainder Theorem, and computes modular exponentiation with repeated squaring.
What Is the Modular Arithmetic Calculator | Modular Inverse, CRT & Power Mod?
Modular arithmetic ('clock arithmetic') studies the remainder after integer division. The notation a mod n means the remainder when a is divided by n. It underlies modern cryptography (RSA, Diffie-Hellman), hash functions, and computer hardware. The Extended Euclidean Algorithm finds modular inverses and Bézout coefficients; the Chinese Remainder Theorem reconstructs a number from its remainders modulo coprime bases.
Formula
Basic: (a op b) mod n
Inverse: a⁻¹ mod n exists iff gcd(a, n) = 1
Power: aᵉ mod n (repeated squaring)
CRT: x ≡ r₁ (mod n₁), x ≡ r₂ (mod n₂) → unique x mod lcm(n₁,n₂)
How to Use
- 1
Choose a mode: Basic, Modular Inverse, Power Mod, or CRT
- 2
For Basic: enter a, operator (+, −, ×, ÷), b, and modulus n
- 3
For Inverse: enter a and n — shows Extended Euclidean steps and Bézout coefficients
- 4
For Power Mod: enter base, exponent, and modulus — uses repeated squaring
- 5
For CRT: enter r₁, n₁, r₂, n₂ and solve the congruence system
- 6
Click Compute and read the result with full step table
Select a mode: Basic for (a op b) mod n, Inverse to find a⁻¹ mod n, Power for fast modular exponentiation aᵉ mod n, or CRT to solve a two-congruence system. Enter the required values and click Compute. Step-by-step working is shown for every mode.
Example Calculation
Example: Modular inverse of 3 mod 7
gcd(3, 7): 7 = 2·3 + 1 → 1 = 7 − 2·3
Bézout: 1 = (−2)·3 + 1·7 → 3⁻¹ ≡ −2 ≡ 5 (mod 7)
Verify: 3 × 5 = 15 = 2·7 + 1 ✓
Frequently Asked Questions
When does a modular inverse exist?
The modular inverse of a modulo n exists if and only if gcd(a, n) = 1, i.e., a and n must be coprime. If gcd(a, n) > 1, there is no integer x such that a·x ≡ 1 (mod n).
Why is repeated squaring used for power mod?
Computing aᵉ mod n by repeated multiplication requires e−1 multiplications. Repeated squaring requires only O(log e) multiplications by squaring the base and halving the exponent, making it feasible for cryptographic exponents with hundreds of digits.
What is the Chinese Remainder Theorem?
The CRT states that if n₁, n₂, … are pairwise coprime, then any system x ≡ rᵢ (mod nᵢ) has a unique solution modulo n₁·n₂·…. This is used in RSA to speed up decryption by working in two smaller modular systems rather than one large one.
What are Bézout coefficients?
For integers a and b, the Extended Euclidean Algorithm finds integers x and y such that ax + by = gcd(a, b). These are called Bézout coefficients. When gcd(a, n) = 1, we have ax + ny = 1, so x is the modular inverse of a mod n.
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.