Modular Arithmetic Calculator - Mod, Power, Inverse & CRT

How to use this tool

1. Choose an operation. Select one of: basic mod, modular exponentiation (aᵇ mod m), modular inverse (a⁻¹ mod m), extended GCD (Bézout coefficients), or Chinese Remainder Theorem.
2. Enter the values. Fill in the required inputs for the chosen operation. All inputs must be integers. The modulus must be a positive integer.
3. Click Calculate. Press Calculate to compute the result instantly with full precision.
4. Review the steps. The step-by-step breakdown shows which algorithm was applied and how the result was derived - useful for learning or verification.

What is modular arithmetic?

Modular arithmetic studies the remainders left when integers are divided by a fixed number called the modulus. Writing a ≡ b (mod m) means a and b have the same remainder when divided by m. All integers from 0 to m−1 form a complete residue system mod m.

Supported operations

• Basic mod: a mod m: always returns a value in [0, m−1].
• Modular exponentiation: aᵇ mod m using fast square-and-multiply, running in O(log b) steps.
• Modular inverse: a⁻¹ mod m via extended Euclidean algorithm. Requires gcd(a, m) = 1.
• Extended GCD: gcd(a, b) plus Bézout coefficients x, y where a·x + b·y = gcd(a, b).
• Chinese Remainder Theorem: Solve simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂).

Applications

• Cryptography: RSA key generation, Diffie-Hellman, elliptic curve cryptography all rely on modular arithmetic.
• Hashing: Hash functions use mod to map large values into fixed-size buckets.
• Calendars: Computing the day of the week uses modular arithmetic (mod 7).
• Error detection: ISBN, IBAN, credit card checksums all use modular computations.

Clock arithmetic visual

The classic way to visualize modular arithmetic is a clock face. A 12-hour clock is arithmetic mod 12. If it is 9 o'clock and you add 8 hours, you don't get 17 - you get 17 mod 12 = 5. Similarly, 17 mod 12 = 5, meaning 17 and 5 are congruent mod 12.

Worked examples

• Modular exponentiation: 3⁵ mod 7. Compute 3¹=3, 3²=9->2, 3⁴=4, 3⁵=3×4=12->5. Answer: 5.
• Modular inverse: 3⁻¹ mod 7. Find x such that 3x ≡ 1 (mod 7). Test: 3×5=15=2×7+1 ->1 (mod 7). Answer: x = 5.
• CRT: x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Combined modulus = 15. Answer: x = 8 (check: 8 mod 3=2 ✓, 8 mod 5=3 ✓).

Fermat's Little Theorem

If p is prime and a is not divisible by p, then:

a^(p-1) ≡ 1 (mod p)

This is foundational to RSA encryption: it guarantees that the encryption and decryption exponents satisfy ed ≡ 1 (mod λ(n)), ensuring the message can be recovered. It also enables fast modular inverse: a⁻¹ ≡ a^(p−2) (mod p) when p is prime.